原始数字魔方(3*3的二维矩阵) 旋转后 得到目标数字魔方(3*3的二维矩阵)
问题描述：原始数字魔方是个3*3的数字矩阵，内部元素从1到9 ，如下：
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
每个子魔方可以进行的旋转操作
现在给定一个目标魔方，问原始魔方最少经过多少次旋转可以得到目标魔方？例如，若目标魔方为
| 5 | 4 | 1 |
| 6 | 2 | 3 |
| 7 | 8 | 9 |
则程序输出应当为3.
程序如下：
1. 输入二维矩阵initArr，其第block[ii]子魔方旋转α度后得到的矩阵rotatedArr。
void MagicCubeRotation(int **initArr, int **rotatedArr, int row, int col, int block, int n)
{int rowBorderLeft = 0, rowBorderRight = 0, colBorderLeft = 0, colBorderRight = 0;if (block == 1){rowBorderLeft = 0; rowBorderRight = 1; colBorderLeft = 0;colBorderRight = 1;}else if(block == 2){rowBorderLeft = 0; rowBorderRight = 1; colBorderLeft = 1;colBorderRight = 2;}else if (block == 3){rowBorderLeft = 1; rowBorderRight = 2; colBorderLeft = 0;colBorderRight = 1;}else if (block == 4){rowBorderLeft = 1; rowBorderRight = 2; colBorderLeft = 1;colBorderRight = 2;}else{cout << "Error input block." << endl;return;}for (int ii=0; ii2. 判断两个二维矩阵是否相等。
bool IsEqual2DMatrix(int **tarArr, int **rotatedArr, int row, int col)
{for(int ii=0; ii3. 判断block[ii]块旋转α度后是否与目标魔方相等。
void GetMagCubeRotatedResult(int **inArr, int **outArr, int **tarArr, int row, int col, int block, int angle, int *flag)
{if (*flag == 1)return;MagicCubeRotation(inArr, outArr, row, col, block, angle);if (IsEqual2DMatrix(tarArr, outArr, row, col)){*flag = 1;}return;
}4. 二维数组拷贝。
void MatrixCopy2D(int **&arr1, int **arr2, int row, int col)
{for (int ii=0; ii5. 计算需要旋转的次数。
void CalcMagicCubeRotationTimes(int **&initArr, int **&outArr, int **&tarArr, int row, int col, int *block, int num, int *angRotate, int count, int depth)
{if ( count > 4 || depth > 4)return ;int ** tmp= new int *[row];int ** tmp2= new int *[row];int flag = 0, lock1 = 1, lock2 = 1;for(int ii = 0; ii < row; ii ++){tmp[ii] = new int[col];tmp2[ii] = new int[col];}MatrixCopy2D(tmp, initArr, row, col);for (int ii=0; ii<4; ++ii){MatrixCopy2D(initArr, tmp, row, col);GetMagCubeRotatedResult(initArr, outArr, tarArr, row, col, block[num], angRotate[ii], &flag);MatrixCopy2D(tmp2, outArr, row, col);// cout << block[num] << "(" << angRotate[ii] << ") ";if ( angRotate[ii] != 0 && lock1){++(count);lock1 = 0;}if (flag){cout << "一共需要旋转" << count << "次" << endl;getchar();getchar();break;}else{if (lock2){++(depth);lock2 = 0;}// cout << depth << "深度时旋转了" << count << "次" << endl; switch(num){case 0:CalcMagicCubeRotationTimes(tmp2, outArr, tarArr, row, col, block, 1, angRotate, count, depth);CalcMagicCubeRotationTimes(tmp2, outArr, tarArr, row, col, block, 2, angRotate, count, depth);CalcMagicCubeRotationTimes(tmp2, outArr, tarArr, row, col, block, 3, angRotate, count, depth);break;case 1:CalcMagicCubeRotationTimes(tmp2, outArr, tarArr, row, col, block, 0, angRotate, count, depth);CalcMagicCubeRotationTimes(tmp2, outArr, tarArr, row, col, block, 2, angRotate, count, depth);CalcMagicCubeRotationTimes(tmp2, outArr, tarArr, row, col, block, 3, angRotate, count, depth);break;case 2:CalcMagicCubeRotationTimes(tmp2, outArr, tarArr, row, col, block, 0, angRotate, count, depth);CalcMagicCubeRotationTimes(tmp2, outArr, tarArr, row, col, block, 1, angRotate, count, depth);CalcMagicCubeRotationTimes(tmp2, outArr, tarArr, row, col, block, 3, angRotate, count, depth);break;case 3:CalcMagicCubeRotationTimes(tmp2, outArr, tarArr, row, col, block, 1, angRotate, count, depth);CalcMagicCubeRotationTimes(tmp2, outArr, tarArr, row, col, block, 2, angRotate, count, depth);CalcMagicCubeRotationTimes(tmp2, outArr, tarArr, row, col, block, 0, angRotate, count, depth);break;default:cout << "Error" << endl; break;} }}for(int ii = 0; ii < row; ii ++){delete [] tmp[ii] ;delete [] tmp2[ii];}return;
}6. 主函数。
int main(int argc, char **argv)
{const int row = 3, col = 3;int mInitArr[][col] = {1,2,3,4,5,6,7,8,9};//int mTarArr[][col] = {4, 1, 3, 5, 2, 6, 7, 8, 9}; //1//int mTarArr[][col] = {2, 5, 3, 1, 4, 6, 7, 8, 9}; //1//int mTarArr[][col] = {2, 4, 5, 1, 6, 3, 7, 8, 9}; //2int mTarArr[][col] = {5, 4, 1, 6, 2, 3, 7, 8, 9}; //3//int mTarArr[][col] = {4, 2, 1, 5, 8, 6, 7, 9, 3}; int block[] = {1, 2, 3, 4};int angRotate[] = {0, 90, 180, 270};int rotateCnt = 0;int minCnt = 100;int judgeContinueFlag = 1;int flag = 0;int count = 0;int depth = 0;int ** initArr= new int *[row];for(int i = 0; i < row; i ++)initArr[i] = new int[col];int ** tarArr= new int *[row];for(int i = 0; i < row; i ++)tarArr[i] = new int[col];int ** outArr= new int *[row];for(int i = 0; i < row; i ++)outArr[i] = new int[col];for (int ii=0; ii7. 输出结果：
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！