自己写得只能适合那些不重复走结点的情况， 跪了
//测试1: 1 2 3 x 4 6 7 5 8 (注意最后一个有空格)结果r d r正确
//测试2：2 3 4 1 5 x 7 6 8 结果not reachable错误！正确答案：ullddrurdllurdruldr
#include#include #include #include using namespace std;char map[3][3];int visit[3][3];typedef struct state{ char action;//从上一个状态 到 当前状态所需的移动路径： u, d, l, r int x;//空格当前的横纵坐标 int y; int prePos;//上一个状态时空格在states的下标 char mapStr[10];//当前状态组成的字符序列};state states[1000];//states[i]代表空格在i位置时的状态const char endState[10] = "12345678x";const int endPos = 8;int moveX[4] = {-1, 1, 0, 0};//上 下 左 右int moveY[4] = {0, 0, -1, 1};bool bfs(state start){ if(strcmp(start.mapStr, endState) == 0){ return true; } queue q; q.push(start); while(!q.empty()){ state cur = q.front(); q.pop(); visit[cur.x][cur.y] = 1;//标记为已访问，防止移动回来 for(int i = 0; i < 4; i++){ int tmpX = cur.x + moveX[i]; int tmpY = cur.y + moveY[i]; if(tmpX >=0 && tmpX <=2 && tmpY >=0 && tmpY <=2 && visit[tmpX][tmpY] == 0){ char newMapStr[10] = {0}; strcpy(newMapStr, cur.mapStr); newMapStr[cur.x * 3 + cur.y] = newMapStr[tmpX * 3 + tmpY] ;//将空格与新位置上的字符互换 newMapStr[tmpX * 3 + tmpY] = 'x'; char action; switch(i){ case 0: action = 'u'; break; case 1: action = 'd'; break; case 2: action = 'l'; break; case 3: action = 'r'; break; } state next; next.action = action;//从cur变到next的action next.x = tmpX; next.y = tmpY; next.prePos = cur.x * 3 + cur.y; strcpy(next.mapStr, newMapStr); states[tmpX * 3 + tmpY] = next; //test //printf("cur is %d --> next is %d\n",next.prePos, tmpX * 3 + tmpY); if(strcmp(newMapStr, endState) == 0){ return true; } q.push(next); } } //visit[cur.x][cur.y] = 0; //test //printf("\n"); } return false;}//测试1: 1 2 3 x 4 6 7 5 8 (注意最后一个有空格)结果r d r正确//测试2：2 3 4 1 5 x 7 6 8 结果not reachable错误！int main(){ freopen("in.txt","r",stdin); memset(visit, 0, sizeof(visit)); memset(map, 0, sizeof(map)); state start; start.x = -1;//必须显示初始化，因为循环中的初始化被视为可能不可达的, fuck！！ start.y = -1; int pos = 0; char mapStr[10]={0}; for(int i = 0; i < 3; i++){ for(int j = 0; j < 3; j++){ scanf("%c ", &map[i][j]);//注意： 输入时的空格也会被读成一个char, fuck！！！ if(map[i][j] == 'x'){ start.x = i; start.y = j; } mapStr[i*3 + j] = map[i][j]; } } mapStr[9] = '\0'; start.prePos = -1; strcpy(start.mapStr, mapStr); states[start.x * 3 + start.y] = start; if(bfs(start)){ stack s; state tmp = states[endPos];//结束状态 while(tmp.prePos != -1){ s.push(tmp); tmp = states[tmp.prePos]; } //printf("%c ", tmp.action); while(!s.empty()){ tmp = s.top(); s.pop(); printf("%c ", tmp.action); } }else{ printf("NOT REACHABLE\n"); } return 0;}