1426: [蓝桥杯][历届试题]九宫重排

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int N = 3010;
  4 map<string, int>m;
  5 string s1, s2;
  6 int ans = 0;
  7 struct node
  8 {
  9     string s;
 10     int step;
 11     int t;
 12 };
 13 void bfs()
 14 {
 15     queue<node>q;
 16     node e;
 17     e.s = s1;
 18     e.step = 0;
 19     for (int i = 0; i < 9; i++)
 20     {
 21         if (e.s[i] == ‘.‘)
 22         {
 23             e.t = i;
 24             break;
 25         }
 26     }
 27     q.push(e);
 28     while (!q.empty())
 29     {
 30         node w = q.front();
 31         q.pop();
 32         if (w.s == s2)
 33         {
 34             cout << w.step << endl;
 35             return;
 36         }
 37         int t = w.t;
 38         if (t + 3 < 9)//下
 39         {
 40             node e;
 41             e = w;
 42             swap(e.s[t], e.s[t + 3]);
 43             if (m[e.s] == 0)
 44             {
 45                 e.step = w.step + 1;
 46                 e.t = t + 3;
 47                 m[e.s]++;
 48                 q.push(e);
 49             }
 50         }
 51         if (t - 3 >= 0)//上
 52         {
 53             node e;
 54             e = w;
 55             swap(e.s[t], e.s[t - 3]);
 56             if (m[e.s] == 0)
 57             {
 58                 e.step = w.step + 1;
 59                 e.t = t-3;
 60                 m[e.s]++;
 61                 q.push(e);
 62             }
 63         }
 64         if (t==1||t==0||t==4||t==3||t==7||t==6)//右
 65         {
 66             node e;
 67             e = w;
 68             swap(e.s[t], e.s[t +1 ]);
 69             if (m[e.s] == 0)
 70             {
 71                 e.step = w.step + 1;
 72                 e.t = t + 1;
 73                 m[e.s]++;
 74                 q.push(e);
 75             }
 76         }
 77         if (t == 1 || t == 2 || t == 4 || t == 5 || t == 7 || t == 8)//左
 78         {
 79             node e;
 80             e = w;
 81             swap(e.s[t], e.s[t - 1]);
 82             if (m[e.s] == 0)
 83             {
 84                 e.t = t - 1;
 85                 m[e.s]++;
 86                 e.step = w.step + 1;
 87                 q.push(e);
 88             }
 89         }
 90     }
 91     if (q.empty())
 92     {
 93         cout << "-1" << endl;
 94     }
 95 }
 96 int main()
 97 {
 98     cin >> s1 >> s2;
 99     m[s1] = 1;
100     bfs();
101     return 0;
102 }