POJ1077 八数码 BFS

BFS 几天的超时...
A*算法不会,哪天再看去了.
  1 /*
  2     倒搜超时,
  3     改成顺序搜超时
  4     然后把记录路径改成只记录当前点的操作,把上次的位置记录下AC..不完整的人生啊
  5 */
  6 
  7 #include <iostream>
  8 #include <queue>
  9 #include <vector>
 10 #include <iterator>
 11 #include <string>
 12 using namespace std;
 13 
 14 const int MAXX_SIZE = 362885;
 15 
 16 int fac[] = {1,1,2,6,24,120,720,5040,40320};
 17 bool used[MAXX_SIZE];
 18 
 19 struct Nod
 20 {
 21     string str;    //数组
 22     int postion9;  //可交换的位置
 23 }nod[MAXX_SIZE];
 24 
 25 struct Step
 26 {
 27     int last;
 28     char c;        //l0, r1, u2, d3
 29 
 30 }step[MAXX_SIZE];
 31 
 32 int dir[][2] = {1,0, -1,0, 0,1, 0,-1 };
 33 
 34 char st[] = {'d', 'u', 'r', 'l'};
 35 
 36 int Kt(string str, int n)
 37 {
 38     int i, j, cnt, sum=0;
 39     for (i=0; i<n; i++)
 40     {
 41         cnt = 0;
 42         for (j=i+1; j<n; j++)
 43             if (str[i] > str[j])
 44                 cnt++;
 45         sum += cnt * fac[n-1-i];
 46     }
 47     return sum;
 48 }
 49 
 50 string InverKt(int sum, int n)
 51 {
 52     int i, j, t;
 53     bool Int[20];
 54     string str;
 55     for (i=0; i<n; i++)
 56     {
 57         t = sum / fac[n-1-i];
 58         for (j=0; j<n; j++)
 59         {
 60             if (Int[j])
 61             {
 62                 if (t == 0)
 63                     break;
 64                 t--;
 65             }
 66         }
 67         str += j+1+'0';
 68         Int[j] = false;
 69         sum %= fac[n-1-i];
 70     }
 71     //str += '';
 72     return str;
 73 }
 74 
 75 
 76 void bfs(string str, int pos)
 77 {
 78     queue<int>que;
 79     
 80     //string str = "123456789";
 81     int i, m, n = Kt(str, 9);
 82     int ii, jj, ti, tj, t;
 83     
 84     nod[n].str = str;
 85     nod[n].postion9 = pos;
 86     step[n].last = -1;
 87     que.push(n);
 88     used[n] = true;
 89 
 90     while (!que.empty())
 91     {
 92         n = que.front();
 93         que.pop();
 94         ii = nod[n].postion9 / 3;
 95         jj = nod[n].postion9 % 3;
 96         for (i=0; i<4; i++)
 97         {
 98             ti = ii + dir[i][0];
 99             tj = jj + dir[i][1];
100             if (ti < 0 || ti > 2 || tj < 0 || tj > 2)
101                 continue;
102             t = ti*3+tj;
103             swap(nod[n].str[nod[n].postion9], nod[n].str[t]);
104             m = Kt(nod[n].str, 9);
105 
106             if (!used[m])
107             {
108                 used[m] = true;
109                 nod[m].str = nod[n].str;
110                 nod[m].postion9 = t;
111                 step[m].last = n;
112                 step[m].c = st[i] ;
113                 //step[m].str = step[n] + st[i]; 超时!
114                 if (m == 0)
115                     return ;
116                 que.push(m);
117             }
118             swap(nod[n].str[nod[n].postion9], nod[n].str[t]);
119         }
120     }
121 }
122 
123 void show(int m)
124 {
125     if (step[m].last == -1)
126         return;
127     show(step[m].last);
128     cout<<step[m].c;
129 }
130 
131 int main()
132 {
133     
134     int i, n=9, m, pos;
135     char c;
136     string str;
137     for (i=0; i<n; i++)
138     {
139         cin>>c;
140         if (c == 'x')
141         {
142             pos = i;
143             c = '9';
144         }
145         str+= c;
146     }
147     bfs(str, pos);
148 //    m = Kt(str, n);
149     if (!used[0])
150         cout<<"unsolvable"<<endl;
151     else
152         show(0);
153     return 0;
154 }
View Code