推箱子 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 8280 Accepted Submission(s): 2397 Problem Description 推箱子是一个很经典的游戏.今天我们来玩一个简单版本.在一个M*N的房间里有一个箱子和一个搬运工,搬运工的工作就是把箱子推到指定的位置,注意,搬运工只能推箱子而不能拉箱子,因此如果箱子被推到一个角上(如图2)那么箱子就不能再被移动了,如果箱子被推到一面墙上,那么箱子只能沿着墙移动. 现在给定房间的结构,箱子的位置,搬运工的位置和箱子要被推去的位置,请你计算出搬运工至少要推动箱子多少格. Input 输入数据的第一行是一个整数T(1<=T<=20),代表测试数据的数量.然后是T组测试数据,每组测试数据的第一行是两个正整数M,N(2<=M,N<=7),代表房间的大小,然后是一个M行N列的矩阵,代表房间的布局,其中0代表空的地板,1代表墙,2代表箱子的起始位置,3代表箱子要被推去的位置,4代表搬运工的起始位置. Output 对于每组测试数据,输出搬运工最少需要推动箱子多少格才能帮箱子推到指定位置,如果不能推到指定位置则输出-1. Sample Input 1 5 5 0 3 0 0 0 1 0 1 4 0 0 0 1 0 0 1 0 2 0 0 0 0 0 0 0 Sample Output 4 Author Ignatius.L & weigang Lee
思路：这道题的思路给了我很大的启发，也让我对与搜索的理解更深了。
首先我们要确定箱子要走的位置，四个方向，那么有以下条件不能走。
1.下个位置越界。
2.下个位置是墙。
如果下个点箱子可以走的情况下，我们再判断人是否可以走到推箱子的位置。假设箱子在(x, y)，箱子下次要走的位置是(x, y + 1)，那么我们就要判断人是否可以走到(x, y - 1)，因为只有这个点才能推着箱子（x，y）走到点（x， y + 1）。那么人要走的情况同样是四个方向，有以下情况不能走。
1.下个位置越界。
2.下个位置是墙。
3.下个位置是箱子，如果是箱子，那么人不能过去。
这样我们是在满足箱子可以走到下一个位置情况下，找到满足人可以走到推箱子的位置。
需要注意的是：刚开始箱子有可能就是终点，在判断人是否可以走到下一个点的时候，有可能起点就是终点。
在这里我错了好久，一直WA。
AC代码：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; #define N 10 int dr[4][2] = {{0, 1},{0, -1},{-1, 0},{1, 0}}; int map[N][N]; int mark[N][N]; int vis[N][N][N][N]; ///前两个坐标代表箱子的坐标， 后两个代表人的位置的坐标 用来标记当前的对应位置是否走过 int Box_x, Box_y, Person_x, Person_y, ex, ey;/// 分别代表箱子开始时的位置，人开始时的位置，以及终点 int m, n, t; ///m行 n列 struct node { int box_x, box_y; int person_x, person_y; int step; } p; struct point { int x, y; } q; int BFS(int sx, int sy, int endx, int endy, int boxx, int boxy) { memset(mark, 0, sizeof(mark)); queue<point>qq; q.x = sx, q.y = sy; qq.push(q); point cur, nex; mark[sx][sy] = 1; while(!qq.empty()) { cur = qq.front(); qq.pop(); if(cur.x == endx&&cur.y == endy) ///注意有可能第一个点就是我们要搜的点 { return 1; } for(int i = 0; i < 4; i++) { nex.x = cur.x + dr[i][0]; nex.y = cur.y + dr[i][1]; if(nex.x >= 0&&nex.x < m&&nex.y >= 0&&nex.y < n&&!mark[nex.x][nex.y]&&map[nex.x][nex.y]!=1) { if(nex.x!=boxx||nex.y!=boxy) { mark[nex.x][nex.y] = 1; qq.push(nex); } } } } return 0; } void bfs() { memset(vis, 0, sizeof(vis)); p.box_x = Box_x, p.box_y = Box_y, p.person_x = Person_x, p.person_y = Person_y, p.step = 0; queue<node>Q; Q.push(p); node now, next; vis[Box_x][Box_y][Person_x][Person_y] = 1; while(!Q.empty()) { now = Q.front(); Q.pop(); if(map[now.box_x][now.box_y] == 3)///有可能箱子就在终点 { printf("%d\n",now.step); return ; } for(int i = 0; i < 4; i++) { next.box_x = now.box_x + dr[i][0]; next.box_y = now.box_y + dr[i][1]; next.person_x = now.box_x - dr[i][0]; next.person_y = now.box_y - dr[i][1]; if(next.box_x < 0||next.box_x >= m||next.box_y < 0||next.box_y >= n) continue; ///箱子接下来走的位置越界 if(map[next.box_x][next.box_y]==1) continue; ///箱子接下来走的位置是墙 if(map[next.person_x][next.person_y]==1) continue; ///人接下来走的位置是墙 if(next.person_x < 0||next.person_x >= m||next.person_y < 0||next.person_y >= n) continue;///人接下来走的位置越界 if(vis[next.box_x][next.box_y][next.person_x][next.person_y]) continue; ///这种状态已经走过 if(BFS(now.person_x, now.person_y, next.person_x, next.person_y, now.box_x, now.box_y)) { vis[next.box_x][next.box_y][next.person_x][next.person_y] = 1; next.step = now.step + 1; Q.push(next); } } } printf("-1\n"); } int main() { while(~scanf("%d",&t)) { while(t--) { scanf("%d%d",&m, &n); for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { scanf("%d",&map[i][j]); if(map[i][j] == 2) { Box_x = i, Box_y = j; } if(map[i][j] == 3) { ex = i, ey = j; } if(map[i][j] == 4) { Person_x = i, Person_y = j; } } } bfs(); } } return 0; }
