USACO Magic Squares 魔板 结题报告

这个题目从一开始我就看错题了，我以为是要从输入的那个矩阵通过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;
}