网站建设服务周到,网站建设技能培训,网页设计制作免费,厦门专业网站建设代理问题描述如下面第一个图的九宫格中#xff0c;放着 1~8 的数字卡片#xff0c;还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动#xff0c;可以形成第二个图所示的局面。我们把第一个图的局面记为#xff1a;12345678.把第二个图的局面记为… 问题描述 如下面第一个图的九宫格中放着 1~8 的数字卡片还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动可以形成第二个图所示的局面。 我们把第一个图的局面记为12345678. 把第二个图的局面记为123.46758 显然是按从上到下从左到右的顺序记录数字空格记为句点。 本题目的任务是已知九宫的初态和终态求最少经过多少步的移动可以到达。如果无论多少步都无法到达则输出-1。 输入格式 输入第一行包含九宫的初态第二行包含九宫的终态。 输出格式 输出最少的步数如果不存在方案则输出-1。 样例输入 12345678.123.46758 样例输出 3 样例输入 13524678.46758123. 样例输出 22 1 #includeiostream2 #includecstring3 #includecstdio4 #includealgorithm5 #includevector6 #includequeue7 #includeset 8 #define N 200059 using namespace std;
10
11 char mp[3][3], gp[3][3];
12 int dir[4][2] {0,1, 1,0, -1,0, 0,-1};
13 char str[10];
14 struct node{
15 int x, y;
16 int step;
17 char cur_mp[3][3];//记录当前图案
18 node(){
19 }
20 node(int x, int y, int step){
21 this-x x;
22 this-y y;
23 this-step step;
24 }
25 };
26 setintst;
27 queuenodeq;
28 bool check(node cur){
29 for(int i0; i3; i)
30 for(int j0; j3; j)
31 if(cur.cur_mp[i][j] ! gp[i][j])
32 return false;
33 return true;
34 }
35
36 int cal(node cur){//每一次移动将会映射到一个不同的整数
37 int ss 0;
38 for(int i0; i3; i)
39 for(int j0; j3; j)
40 if(cur.cur_mp[i][j] ! .)
41 ss ss*10(cur.cur_mp[i][j]-0);
42 else ss ss*109;
43 return ss;
44 }
45
46 void bfs(){
47 st.clear();
48 if(!q.empty())
49 st.insert(cal(q.front()));
50 while(!q.empty()){
51 node cur q.front();
52 q.pop();
53 if(check(cur)) {
54 coutcur.stependl;
55 return ;
56 }
57
58 for(int i0; i4; i){
59 int xx cur.xdir[i][1];
60 int yy cur.ydir[i][0];
61 if(xx0 || xx2 || yy0 || yy2) continue;
62 node nt node(xx, yy, cur.step1);
63 memcpy(nt.cur_mp, cur.cur_mp, sizeof(cur.cur_mp));
64 nt.cur_mp[cur.x][cur.y]^nt.cur_mp[xx][yy];
65 nt.cur_mp[xx][yy]^nt.cur_mp[cur.x][cur.y];
66 nt.cur_mp[cur.x][cur.y]^nt.cur_mp[xx][yy];
67 int val cal(nt);
68 if(st.find(val) ! st.end()) continue;
69 st.insert(val);
70 q.push(nt);
71 }
72 }
73 cout-1endl;
74 }
75
76 int main() {
77 while(cinstr){
78 int bx, by;
79 while(!q.empty()) q.pop();
80 int len 0;
81 for(int i0; i3; i)
82 for(int j0; j3; j){
83 mp[i][j] str[len];
84 if(mp[i][j] .) bxi, byj;
85 }
86 node cur node(bx, by, 0);
87 memcpy(cur.cur_mp, mp, sizeof(mp));
88 q.push(cur);
89 cinstr;
90 len 0;
91 for(int i0; i3; i)
92 for(int j0; j3; j)
93 gp[i][j] str[len];
94 bfs();
95 }
96 return 0;
97 } 转载于:https://www.cnblogs.com/hujunzheng/p/4345489.html
