#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 人评分
2006年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:606 |
C二级辅导-阶乘数列 (C++代码)浏览:1923 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:699 |
C语言程序设计教程(第三版)课后习题11.5 (C语言代码)浏览:1011 |
程序员的表白 (C语言代码)浏览:1408 |
简单的a+b (C语言代码)浏览:778 |
C语言训练-大、小写问题 (C语言代码)浏览:2416 |
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)浏览:460 |
c primer plus 第十二章 12.1小节浏览:394 |
A+B for Input-Output Practice (III) (C语言代码)浏览:589 |