Question

3*3拼图游戏算法实现（C++的代码）

．基本要求
设一副图是由几个部分拼凑成的，现在要把这些散块拼凑成一副完整的图片
可以用数字代替各部分图片
比如初始矩阵为3*3
{1, 2, 3
4, 5, 6
7, 8, }
要求从目标矩阵
{1, 2, 7
3, 6, 4
5, 8, }
逐步变化到初始矩阵
可以任意输入目标矩阵

Answer 1

我这个程序是求还原矩阵所需的最少步数，你只要稍作修改就可以了。把路径记录下来输出。
#include <stdio.h>
#include <memory>
#include <queue>
#include <string>

using namespace std;

struct Board
{
int pos[5][5];
string step;
};
Board origin;
bool st[362880];

int direction[4][2] = {-1, 0, 1, 0, 0, 1, 0, -1};//swap 0 with dowm, up, right, left

void Reset()
{
int i, j;
memset(origin.pos, 255, sizeof(origin.pos));
for (i=1; i<4; i++)
{
for (j=1; j<4; j++)
{
origin.pos[i][j] = (i-1)*3 + j;
}
}
origin.pos[3][3] = 0;
}

bool Equal(Board b1, Board b2)
{
int i, k;
for (i=1; i<4; i++)
{
for (k=1; k<4; k++)
{
if (b1.pos[i][k] != b2.pos[i][k])
{
return false;
}
}
}
return true;
}

int main()
{
int cases;
int i, k, m, l;
Board current, dest;
Reset();
scanf("%d", &cases);
for (i=0; i<cases; i++)
{
queue< Board > que;
for (m=1; m<4; m++)
{
for (k=1; k<4; k++)
{
scanf("%d", &dest.pos[m][k]);
}
}
if(Equal(origin, dest))
{
printf("0\n");
continue;
}
que.push(origin);
while (false == que.empty())
{
current = que.front();
que.pop();
int len = current.step.length();
if (len == 5)
{
break;
}
for (m=1; m<4; m++)
{
for (k=1; k<4; k++)
{
if (0 == current.pos[m][k])
{
goto out;
}
}
}
out:
for (l=0; l<4; l++)
{
if (0==l && current.step[len-1] == '1')
{
continue;
}
if (1==l && current.step[len-1] == '0')
{
continue;
}
if (2==l && current.step[len-1] == '3')
{
continue;
}
if (3==l && current.step[len-1] == '2')
{
continue;
}

if (current.pos[m+direction[l][0]][k+direction[l][1]]>0)
{
swap(current.pos[m][k], current.pos[m+direction[l][0]][k+direction[l][1]]);
current.step += l + '0';
if (Equal(current, dest))
{
goto print;
}
else
{
que.push(current);
current.step.resize(current.step.length()-1);
swap(current.pos[m][k], current.pos[m+direction[l][0]][k+direction[l][1]]);
}
}
}
}
print:
printf("%d\n", current.step.length());
}
return 0;
}