UVa-1604 Cubic Eight-Puzzle

  1 #include <bits/stdc++.h>
  2 #define _for(i,a,b) for(int i = (a);i < (b);i ++)
  3 using namespace std;
  4 struct cell
  5 {
  6     int t;
  7     int f;
  8 };
  9 struct State
 10 {
 11     cell c[9];
 12     int d;
 13 };
 14 
 15 const int maxstate = 1000000;
 16 State st,goal;
 17 int dist[maxstate];
 18 
 19 const int dx[] = {-1,1,0,0};
 20 const int dy[] = {0,0,1,-1};
 21 
 22 int diff(State s)
 23 {
 24     int cnt = 0;
 25     _for(i,0,9)
 26     {
 27         if(s.c[i].t != goal.c[i].t) cnt ++;
 28     }
 29     return cnt;
 30 }
 31 
 32 bool limit(int x,int y)
 33 {
 34     return x>=0&&x<3&&y>=0&&y<3;
 35 }
 36 
 37 int Hash[7][7][7][7][7][7][7][7][7];
 38 void init_lookup_table()
 39 {
 40     memset(Hash,0,sizeof(Hash));
 41 }
 42 bool try_to_insert(State s)
 43 {
 44     int v = 0;
 45     int index[9] {0};
 46     _for(i,0,9)
 47         if(s.c[i].t==0&&s.c[i].f==1)
 48             index[i] = 0;
 49         else if(s.c[i].t==1&&s.c[i].f==0)
 50             index[i] = 1;
 51         else if(s.c[i].t==1&&s.c[i].f==2)
 52             index[i] = 2;
 53         else if(s.c[i].t==2&&s.c[i].f==1)
 54             index[i] = 3;
 55         else if(s.c[i].t==0&&s.c[i].f==2)
 56             index[i] = 4;
 57         else if(s.c[i].t==2&&s.c[i].f==0)
 58             index[i] = 5;
 59         else if(s.c[i].t<0)
 60            index[i] = 6;
 61     int &shash = Hash[index[0]][index[1]][index[2]][index[3]][index[4]][index[5]][index[6]][index[7]][index[8]];
 62     if(shash)
 63         return false;
 64     shash = 1;
 65     return true;
 66 }
 67 
 68 int bfs()
 69 {
 70     init_lookup_table();
 71     queue<State> q;
 72     st.d = 0;
 73     q.push(st);
 74     while(!q.empty())
 75     {
 76         State s = q.front();q.pop();
 77         if(diff(s)+s.d>31) continue;
 78         if(!diff(s)) return s.d;
 79         int z;
 80         for(z = 0; z < 9; z ++) if(s.c[z].t<0) break;
 81         int x = z/3,y = z%3;
 82         _for(d,0,4)
 83         {
 84             int newx = x+dx[d];
 85             int newy = y+dy[d];
 86             int newz = newx*3+newy;
 87             if(limit(newx,newy))
 88             {
 89                 State t;
 90                 memcpy(&t,&s,sizeof(s));
 91                 if(newx==x)
 92                     t.c[z] = (cell){3-s.c[newz].t-s.c[newz].f,s.c[newz].f};
 93                 else if(newy==y)
 94                     t.c[z] = (cell){s.c[newz].f,s.c[newz].t};
 95                 t.c[newz] = (cell){-1,-1};
 96                 t.d = s.d+1;
 97                 if(try_to_insert(t)) q.push(t);
 98             }
 99         }
100     }
101     return -1;
102 }
103 
104 int main()
105 {
106     int tx,ty;
107     while(scanf("%d%d",&tx,&ty)==2&&tx!=0)
108     {
109         _for(i,0,9) st.c[i] = (cell){0,1};
110         st.c[(ty-1)*3+tx-1] = (cell){-1,-1};
111         _for(i,0,9)
112         {
113             char c;
114             cin >> c;
115             if(c=='E')    goal.c[i].t = -1;
116             else if(c=='W') goal.c[i].t = 0;
117             else if(c=='R') goal.c[i].t = 1;
118             else if(c=='B') goal.c[i].t = 2;
119         }
120         int ans = bfs();
121         if(ans>=0)    printf("%d
",ans);
122         else printf("-1
");
123     }
124     return 0;
125 }