题目

大家一定玩过“推箱子”这个经典的游戏。具体规则就是在一个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;

程序分为两步走：

1. 人还没到箱子处，人走，箱子不动
2. 人到达箱子处，人和箱子一起动

表示点 (x,y) 到点 (bx,by)之前已经走过的步数为1。
用队列来存储待搜索的点。
最坏的情况是搜索完全部的点后不能到达终点， 所以队列不为空时会一直进行下去。
每次分四个方向走，所以是一个四层循环。
第一个if条件判断的是是否到达了目的地处，第二个if条件第一次执行是到了箱子处，到达之后，人开始推着箱子前进，所有人和箱子始终是一个方向的，就有了

st[nx][ny][nnx][nny] = st[x][y][bx][by] + 1

接下来人就换着方向推箱子去找终点