題目
大家一定玩過“推箱子”這個經(jīng)典的游戲。具體規(guī)則就是在一個N*M的地圖上，有1個玩家、1個箱子、1個目的地以及若干障礙，其余是空地。玩家可以往上下左右4個方向移動，但是不能移動出地圖或者移動到障礙里去。如果往這個方向移動推到了箱子，箱子也會按這個方向移動一格，當(dāng)然，箱子也不能被推出地圖或推到障礙里。當(dāng)箱子被推到目的地以后，游戲目標(biāo)達(dá)成?，F(xiàn)在告訴你游戲開始是初始的地圖布局，請你求出玩家最少需要移動多少步才能夠?qū)⒂螒蚰繕?biāo)達(dá)成。
輸入描述
每個測試輸入包含1個測試用例
第一行輸入兩個數(shù)字N，M表示地圖的大小。其中0<N，M<=8。
接下來有N行，每行包含M個字符表示該行地圖。其中 . 表示空地、X表示玩家、*表示箱子、#表示障礙、@表示目的地。
每個地圖必定包含1個玩家、1個箱子、1個目的地。
輸出描述
輸出一個數(shù)字表示玩家最少需要移動多少步才能將游戲目標(biāo)達(dá)成。當(dāng)無論如何達(dá)成不了的時(shí)候，輸出-1。
輸入例子
4 4
....
..*@
....
.X..
6 6
...#..
......
*##..
..##.#
..X...
.@#...
輸出例子
3
11
問題分析
這題是看了網(wǎng)上的解答才知道是BFS問題，自己一開始用的遞歸沒做出來
下面的代碼來自 http://blog.csdn.net/u010009169/article/details/60892521 [如有侵權(quán)，請聯(lián)系我刪除]
代碼
#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]是一個思維數(shù)組，用來存放當(dāng)前點(diǎn)到終點(diǎn)已經(jīng)走過了多少步，例如
st[x][y][bx][by] = 1;
程序分為兩步走：
- 人還沒到箱子處，人走，箱子不動
- 人到達(dá)箱子處，人和箱子一起動
表示點(diǎn) (x,y) 到點(diǎn) (bx,by)之前已經(jīng)走過的步數(shù)為1。
用隊(duì)列來存儲待搜索的點(diǎn)。
最壞的情況是搜索完全部的點(diǎn)后不能到達(dá)終點(diǎn)， 所以隊(duì)列不為空時(shí)會一直進(jìn)行下去。
每次分四個方向走，所以是一個四層循環(huán)。
第一個if條件判斷的是是否到達(dá)了目的地處，第二個if條件第一次執(zhí)行是到了箱子處，到達(dá)之后，人開始推著箱子前進(jìn)，所有人和箱子始終是一個方向的，就有了
st[nx][ny][nnx][nny] = st[x][y][bx][by] + 1
接下來人就換著方向推箱子去找終點(diǎn)
