题目
大家一定玩过“推箱子”这个经典的游戏。具体规则就是在一个N*M的地图上，有1个玩家、1个箱子、1个目的地以及若干障碍，其余是空地。玩家可以往上下左右4个方向移动，但是不能移动出地图或者移动到障碍里去。如果往这个方向移动推到了箱子，箱子也会按这个方向移动一格，当然，箱子也不能被推出地图或推到障碍里。当箱子被推到目的地以后，游戏目标达成。现在告诉你游戏开始是初始的地图布局，请你求出玩家最少需要移动多少步才能够将游戏目标达成。
输入描述
每个测试输入包含1个测试用例
第一行输入两个数字N，M表示地图的大小。其中0<N，M<=8。
接下来有N行，每行包含M个字符表示该行地图。其中 . 表示空地、X表示玩家、*表示箱子、#表示障碍、@表示目的地。
每个地图必定包含1个玩家、1个箱子、1个目的地。
输出描述
输出一个数字表示玩家最少需要移动多少步才能将游戏目标达成。当无论如何达成不了的时候，输出-1。
输入例子
4 4
....
..*@
....
.X..
6 6
...#..
......
*##..
..##.#
..X...
.@#...
输出例子
3
11
问题分析
这题是看了网上的解答才知道是BFS问题，自己一开始用的递归没做出来
下面的代码来自 http://blog.csdn.net/u010009169/article/details/60892521 [如有侵权，请联系我删除]
代码
#include <iostream>
#include <vector>
#include <queue>
using std::vector;
using std::queue;
using std::cin;
using std::cout;
/*
4 4
....
..*@
....
.X..
*/
int st[10][10][10][10];
int x, y, bx, by, tx, ty;
int m, n;
vector<vector<char>> mm;
bool valid(int x, int y) {
//cout <<m<<" "<<n<<"-"<<endl;
if (x >= 0 && x < m && y >= 0 && y < n && mm[x][y] != '#')return true;
return false;
}
int main() {
cin >> m >> n;
mm = std::vector<std::vector<char>>(m, vector<char>(n));
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
char t;
cin >> t;
if (t == 'X') {
x = i;
y = j;
// cout <<x<<" "<<y<<endl;
}
if (t == '*') {
bx = i;
by = j;
}
if (t == '@') {
tx = i;
ty = j;
}
mm[i][j] = t;
}
// record every state of the
//左，右，下，上
vector<vector<int>> next = {{-1, 0},{1, 0},{0, 1},{0, -1}};
queue<vector<int>> que;
que.push({x, y, bx, by});
st[x][y][bx][by] = 1;
while (!que.empty()) {
vector<int> t = (vector<int> &&) que.front();
que.pop();
x = t[0];
y = t[1];
bx = t[2];
by = t[3];
for (int i = 0; i < next.size(); i++) {
int nx = x + next[i][0], ny = y + next[i][1];
int nnx = nx + next[i][0], nny = ny + next[i][1];
if (valid(nx, ny) && (nx != bx || ny != by) && st[nx][ny][bx][by] == 0) {
st[nx][ny][bx][by] = st[x][y][bx][by] + 1;
que.push({nx, ny, bx, by});
continue;
} else if (nx == bx && ny == by && valid(nnx, nny) && st[nx][ny][nnx][nny] == 0) {
st[nx][ny][nnx][nny] = st[x][y][bx][by] + 1;
if (mm[nnx][nny] == '@') {
cout << st[nx][ny][nnx][nny] - 1;
return 0;
}
que.push({nx, ny, nnx, nny});
}
}
}
cout << -1;
return 0;
}
代码分析
st[10][10][10][10]是一个思维数组，用来存放当前点到终点已经走过了多少步，例如
st[x][y][bx][by] = 1;
程序分为两步走：
- 人还没到箱子处，人走，箱子不动
- 人到达箱子处，人和箱子一起动
表示点 (x,y) 到点 (bx,by)之前已经走过的步数为1。
用队列来存储待搜索的点。
最坏的情况是搜索完全部的点后不能到达终点， 所以队列不为空时会一直进行下去。
每次分四个方向走，所以是一个四层循环。
第一个if条件判断的是是否到达了目的地处，第二个if条件第一次执行是到了箱子处，到达之后，人开始推着箱子前进，所有人和箱子始终是一个方向的，就有了
st[nx][ny][nnx][nny] = st[x][y][bx][by] + 1
接下来人就换着方向推箱子去找终点
