题目描述：

给你一个迷宫，有墙，空地，一个人，一个箱子，一个按钮，一个出口。

任务：把箱子推到按钮地方，出口才能打开，然后人从出口出去。

问你：能不能出去，能的话，最少需要几步。

解题报告：

广搜，用的类似spfa的结构进行广搜，把箱子和人看成一个整体，

ans[x][y][a][b]表示人在x，y的位置，箱子在a，b的位置的最少步数是多少，状态最多400*400.

最后输出ans[出口x][出口y][按钮a][按钮b]的结果即可。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cmath>

using namespace std;

int ans[20][20][20][20];

int n, m;

char x[30][30];

int move[4][2] = {0, -1, 0, 1, -1, 0, 1, 0};

int rx, ry, bx, by, ex, ey, ox, oy;

struct pint

{

    pint(int i, int j, int k, int l)

    {

        a = i, b = j, c = k, d = l;

    }

    pint(){}

    int a, b, c, d;

}que[900 * 900];

int spfa()

{

    ans[rx][ry][bx][by] = 0;

    int head = 0, tail = 0;

    que[tail++] = pint(rx, ry, bx, by);

    while(head != tail)

    {

        pint tmp = que[head++];

        if (head == 900 * 900) head = 0;

        for(int i = 0; i < 4; i++)

        {

            int tmpx = tmp.a + move[i][0], tmpy = tmp.b + move[i][1];

            if (tmpx >= 0 && tmpx < n && tmpy >= 0 && tmpy < m && x[tmpx][tmpy] != '#')

            {

                if (x[tmpx][tmpy] == 'd' && tmp.c == ox && tmp.d == oy)

                {

                    return ans[tmp.a][tmp.b][tmp.c][tmp.d] + 1;

                }

                if (x[tmpx][tmpy] != 'd')

                {

                    if (tmp.c == tmpx && tmp.d == tmpy)

                    {

                        int tmpx2 = tmp.c + move[i][0], tmpy2 = tmp.d + move[i][1];

                        if (tmpx2 >= 0 && tmpx2 < n && tmpy2 >= 0 && tmpy2 < m && x[tmpx2][tmpy2] != '#'

                            && x[tmpx2][tmpy2] != 'd' && ans[tmpx][tmpy][tmpx2][tmpy2] == -1)

                        {

                            ans[tmpx][tmpy][tmpx2][tmpy2] = ans[tmp.a][tmp.b][tmp.c][tmp.d] + 1;

                            que[tail++] = pint(tmpx, tmpy, tmpx2, tmpy2);

                            if (tail == 900 * 900) tail = 0;

                        }

                    }

                    else if (ans[tmpx][tmpy][tmp.c][tmp.d] == -1)

                    {

                        ans[tmpx][tmpy][tmp.c][tmp.d] = ans[tmp.a][tmp.b][tmp.c][tmp.d] + 1;

                        que[tail++] = pint(tmpx, tmpy, tmp.c, tmp.d);

                        if (tail == 900 * 900) tail = 0;

                    }

                }

            }

        }

    }

    return -1;

}

int main()

{

    while(scanf("%d%d", &n, &m) && (n || m))

    {

        for(int i = 0; i < n; i++) scanf("%s", x[i]);

        for(int i = 0; i < n; i++) for(int j = 0; j < m; j++)

            if (x[i][j] == '@'){rx = i, ry = j;}

            else if (x[i][j] == 'd'){ex = i, ey = j;}

            else if (x[i][j] == 'x'){bx = i, by = j;}

            else if (x[i][j] == 'b'){ox = i, oy = j;}

        memset(ans, -1, sizeof(ans));

        int jeo = spfa();

        if (jeo == -1) printf("No Way!\n");

        else printf("%d\n", jeo);

    }

    return 0;

}