这个题目从一开始我就看错题了,我以为是要从输入的那个矩阵通过ABC三种方式变换到最初的矩阵(1,2,3,4,5,6,7,8),后来才知道是要从最初的矩阵通过变换到目标矩阵(即输入的)。不过看错提了我还是没做出来,就直接看了标称,标称里面的encode函数看了几次都没看懂,最后打算自己写一个encode函数,毕竟它的功能就是康拓展开,就是一个Hash函数。接下来就介绍我的解题思路:
首先,分析程序的上界,因为一共有8个方格,每个方格又有8种数据,但是又不能重复,根据乘法原理可以计算出一共有40320(即8!)种不同的矩阵,于是我用dist[40320]来存储所有矩阵通过多少步可以逆向(顺向是{1,2,3,4,5,6,7,8}变成输入的,我这里是从输入的变成{1,2,3,4,5,6,7,8})变换成初始状态。然后使用一个函数Hash(即上面的encode函数)来讲矩阵转换成dist的下标。
然后主程序先让dist[目标状态(输入的矩阵)] = 1;,在输出时再减一(至于为什么等于1而不是0看下面。)然后试用BFS对所有的状态进行搜索每遇到一个dist中为0的状态(上面目标状态是从1开始的原因就在这里,不然的话目标状态又会变成别的数字),直到遇到初始状态再停止。
输入dist[初始状态]的值减一(因为dist[目标状态]等于一而不是零)。
最后通过dist之间的关系再输出步骤。
具体代码如下:
/*
LANG: C
ID: zqynux2
PROG: msquare
*/
#include <stdio.h>
#include <string.h>
#define MAX 40320
int dist[40320];
int hash(int *board)
{
int i, j;
int look[8] = {0, 1, 2, 3, 4, 5, 6, 7};
int mult[8] = {1, 8, 8*7, 8*7*6, 8*7*6*5, 8*7*6*5*4,
8*7*6*5*4*3, 8*7*6*5*4*3*2};
int rv = 0;
for(i = 0; i < 8; i++){
rv += look[board[i]] * mult[i];
for(j = board[i] + 1; j < 8; j++){
look[j]--;
}
}
return rv;
}
int ways[3][8] = {{8, 7, 6, 5, 4, 3, 2, 1}, {4, 1, 2, 3, 6, 7, 8, 5},
{1, 7, 2, 4, 5, 3, 6, 8}};
void change(int *to, int *from, int way)
{
int i;
for(i = 0; i < 8; i++){
to[i] = from[ways[way][i] - 1];
}
}
void rechange(int *to, int *from, int way)
{
int i;
for(i = 0; i < 8; i++){
to[ways[way][i] - 1] = from[i];
}
}
int queue[MAX][8];
void count(int *board)
{
int head = 0, tail = 1;
int t, d, i;
memcpy(queue[0], board, sizeof(int [8]));
t = dist[hash(board)] = 1;
while(1){
t = dist[hash(queue[head])];
for(i = 0; i < 3; i++){
rechange(queue[tail], queue[head], i);
d = hash(queue[tail]);
if(dist[d] == 0){
// tail = (tail + 1) % MAX;
tail++; //这一句比上面一句快一些, 但是要求queue数组大些
dist[d] = t + 1;
}
if(d == 0){
return ;
}
}
// head = (head + 1) % MAX;
head++; //这一句比上面一句快一些, 但是要求queue数组大些
}
}
void output(int t)
{
int board[8];
int tmp[8];
int i;
for(i = 0; i < 8; i++){
board[i] = i;
}
while(t > 1){
for(i = 0; i < 3; i++){
change(tmp, board, i);
if(dist[hash(tmp)] == t - 1){
t--;
break;
}
}
memcpy(board, tmp, sizeof(tmp));
printf(%c, i + \'A\');
}
printf(\\n);
}
int main(void)
{
int i;
int board[8];
freopen(msquare.in, r, stdin);
freopen(msquare.out, w, stdout);
for(i = 0; i < 8; i++){
scanf(%d, board + i);
board[i]--; //忘记这里了
}
count(board);
for(i = 0; i < 8; i++){
board[i] = i;
}
printf(%d\\n, i = dist[hash(board)] - 1);
output(i + 1);
return 0;
}