藍橋杯歷屆試題九宮重排

問題描述

如下面第一個圖的九宮格中，放著 1~8 的數字卡片，還有一個格子空著。與空格子相鄰的格子中的卡片可以移動到空格中。經過若干次移動，可以形成第二個圖所示的局面。

　　我們把第一個圖的局面記為：12345678.
　　把第二個圖的局面記為：123.46758
　　顯然是按從上到下，從左到右的順序記錄數字，空格記為句點。
　　本題目的任務是已知九宮的初態和終態，求最少經過多少步的移動可以到達。如果無論多少步都無法到達，則輸出-1。

輸入格式

輸入第一行包含九宮的初態，第二行包含九宮的終態。

輸出格式

輸出最少的步數，如果不存在方案，則輸出-1。

樣例輸入

12345678.
123.46758

樣例輸出

樣例輸入

13524678.
46758123.

樣例輸出

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<vector>
 6 #include<queue>
 7 #include<set> 
 8 #define N 20005
 9 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 set<int>st;
27 queue<node>q;
28 bool check(node cur){
29     for(int i=0; i<3; ++i)
30         for(int j=0; j<3; ++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 i=0; i<3; ++i)
39         for(int j=0; j<3; ++j)
40             if(cur.cur_mp[i][j] != '.')
41                 ss = ss*10+(cur.cur_mp[i][j]-'0');
42             else ss = ss*10+9;
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             cout<<cur.step<<endl;
55             return ;
56         }
57         
58         for(int i=0; i<4; ++i){
59             int xx = cur.x+dir[i][1];
60             int yy = cur.y+dir[i][0];
61             if(xx<0 || xx>2 || yy<0 || yy>2) continue;
62             node nt = node(xx, yy, cur.step+1);
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<<-1<<endl;
74 }
75 
76 int main() {
77     while(cin>>str){
78         int bx, by;
79         while(!q.empty()) q.pop();
80         int len = 0;
81         for(int i=0; i<3; ++i)
82             for(int j=0; j<3; ++j){
83                 mp[i][j] = str[len++];
84                 if(mp[i][j] == '.') bx=i, by=j;
85             }
86         node cur = node(bx, by, 0);
87         memcpy(cur.cur_mp, mp, sizeof(mp));
88         q.push(cur);
89         cin>>str;
90         len = 0;
91         for(int i=0; i<3; ++i)
92             for(int j=0; j<3; ++j)
93                 gp[i][j] = str[len++];
94         bfs();
95     }
96     return 0;
97 }

轉載于:https://www.cnblogs.com/hujunzheng/p/4345489.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/531526.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/531526.shtml
英文地址，請注明出處：http://en.pswp.cn/news/531526.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！