#include<cstdio> #include<cstring> #include<set> using namespace std; typedef int State[9]; const int MAXSTATE = 1000000; State st[MAXSTATE], goal; int dist[MAXSTATE]; set<int> vis; void init_lookup_table() { vis.clear(); } int try_to_insert(int s) { int v = 0; for(int i = 0; i < 9; i++) v = v * 10 + st[s][i]; if(vis.count(v)) return 0; vis.insert(v); return 1; } const int dx[] = {-1, 1, 0, 0}; const int dy[] = {0, 0, -1, 1}; int bfs() { init_lookup_table(); int front = 1, rear = 2; while(front < rear) { State& s = st[front]; if(memcmp(goal, s, sizeof(s)) == 0) return front; int z; for(z = 0; z < 9; z++) if(!s[z]) break; int x = z/3, y = z%3; for(int d = 0; d < 4; d++) { int newx = x + dx[d]; int newy = y + dy[d]; int newz = newx * 3 + newy; if(newx >= 0 && newx < 3 && newy >= 0 && newy < 3) { State& t = st[rear]; memcpy(&t, &s, sizeof(s)); t[newz] = s[z]; t[z] = s[newz]; dist[rear] = dist[front] + 1; if(try_to_insert(rear)) rear++; } } front++; } return 0; } int main() { char str[9]; scanf("%s",str); for(int i=0;i<9;i++) //st[1]是初始状态 if( str[i] !='.' ) st[1][i]=str[i]-'0'; else st[1][i]=0; scanf("%s",str); for(int i=0;i<9;i++)//goal 是目标状态 if(str[i]!='.') goal[i]=str[i]-'0'; else goal[i]=0; int ans = bfs(); if(ans > 0) printf("%d\n", dist[ans]); else printf("-1\n"); return 0; }
0.0分
4 人评分
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:1884 |
C语言考试练习题_排列 (C语言代码)浏览:1315 |
数列排序 (C语言代码)浏览:827 |
C语言程序设计教程(第三版)课后习题8.1 (C语言代码)浏览:438 |
妹子杀手的故事 (C语言代码)浏览:1216 |
WU-整数平均值 (C++代码)浏览:1237 |
IP判断 (C语言代码)浏览:761 |
输出九九乘法表 (C语言代码)浏览:1048 |
简单的a+b (C语言代码)浏览:818 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:740 |