[HDU 1254] 推箱子

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1254
  1 #include<cstdio>
  2 #include<queue>
  3 #include<cstring>
  4 using namespace std;
  5 
  6 #define INF 0xfffffff
  7 
  8 const int maxn = 10;
  9 int go[4][2] = {0,1,0,-1,1,0,-1,0};
 10 int maze[10][10];
 11 int vis[10][10][10][10]; //是由人和箱子的位置这两个状态共同决定
 12 int m,n;
 13 
 14 struct Point
 15 {
 16     int x,y;
 17     int bx,by;
 18     int cnt;
 19 }P;
 20 
 21 //用这个函数替代memset(),不然会导致wronganswer
 22 void init()
 23 {
 24     for(int i=0; i<maxn; i++)
 25         for(int j=0; j<maxn; j++)
 26             for(int k=0; k<maxn; k++)
 27                 for(int p=0; p<maxn; p++)
 28                     vis[i][j][k][p] = INF;
 29 }
 30 
 31 bool OKman(Point s)
 32 {
 33     return s.x>=0 && s.x<m && s.y>=0 && s.y<n && maze[s.x][s.y]!=1 && s.cnt < vis[s.x][s.y][s.bx][s.by];
 34 }
 35 
 36 bool OKbox(Point s)
 37 {
 38     return s.bx>=0 && s.bx<m && s.by>=0 && s.by<n && maze[s.bx][s.by]!=1 && s.cnt < vis[s.x][s.y][s.bx][s.by];
 39 }
 40 
 41 int BFS()
 42 {
 43     Point Pn;
 44     queue<Point> Q;
 45     Q.push(P);
 46     int ans = INF;
 47     vis[P.x][P.y][P.bx][P.by] = 1;
 48     while(!Q.empty())
 49     {
 50         P = Q.front();
 51         Q.pop();
 52         if(maze[P.bx][P.by] == 3)
 53         {
 54             ans = min(ans,P.cnt);
 55         }
 56         for(int i=0;i<4;i++)
 57         {
 58             Pn = P;
 59             Pn.x += go[i][0];
 60             Pn.y += go[i][1];
 61             if(OKman(Pn)) //判断人走下一步是否合法
 62             {
 63                 if(Pn.x == Pn.bx && Pn.y == Pn.by) //在人走下一步合法的条件下,判断人和箱子是否重合,重合就得移动箱子
 64                 {
 65                     Pn.bx += go[i][0];
 66                     Pn.by += go[i][1];
 67                     Pn.cnt++;
 68                     if(OKbox(Pn)) //判断箱子走的下一步是否合法,合法就加入队列
 69                     {
 70                         vis[Pn.x][Pn.y][Pn.bx][Pn.by] = Pn.cnt;
 71                         Q.push(Pn);
 72                     }
 73                 }
 74                 else //如果人和箱子不重合,也就是人还不能推箱子
 75                 {
 76                     vis[Pn.x][Pn.y][Pn.bx][Pn.by] = Pn.cnt;
 77                     Q.push(Pn);
 78                 }
 79             }
 80         }
 81     }
 82     return ans;
 83 }
 84 int main()
 85 {
 86     int T;
 87     scanf("%d",&T);
 88     while(T--)
 89     {
 90         init();
 91         scanf("%d%d",&m,&n);
 92         for(int i=0;i<m;i++)
 93             for(int j=0;j<n;j++)
 94             {
 95                 scanf("%d",&maze[i][j]);
 96                 if(maze[i][j] == 4)
 97                     P.x=i,P.y=j,P.cnt=0;
 98                 else if(maze[i][j] == 2)
 99                     P.bx=i,P.by=j;
100             }
101 //        memset(vis,INF,sizeof(vis));  用memset会导致wronganswer,原因后续跟上.
102         int k = BFS();
103         if(k == INF)
104             k = -1;
105         printf("%d
",k);
106     }
107     return 0;
108 }