hdu1254推箱子(BFS)

題目鏈接：hdu1254

/*
用廣搜尋找最小步數，推箱子需要滿足以下幾個條件：
1.人能走到推箱子的那個位置
2.人不能穿過箱子.
3.箱子可以回到前一狀態的位置，但不是同一方向回到的
*/
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int d[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int map[8][8];
int v[8][8][5];//第三維表示箱子在（i,j）時，是由哪個方向推過來的
int flag;
int n,m,ex,ey,sx,sy,rx,ry;
struct node
{
    int x, y;
    int step;
    int rx, ry;//表示箱子在(x,y)時，箱子之前的位置，也就是人推完箱子後，站在箱子原來的位置
    friend bool operator < (node a,node b)
    {
        return a.step > b.step;
    }
};
bool judge(int x, int y)
{
    if(x < 0 || x >= n || y < 0 || y >= m) return true;
    return false;
}
int p_bfs(int sx, int sy, int ex, int ey, int jx, int jy)
{

    bool f[8][8];
    memset(f, false, sizeof(f));
    priority_queue  q;
    node s, tmp;
    s.x = sx;
    s.y = sy;
    f[sx][sy] = true;
    s.step = 0;
    q.push(s);
    while(!q.empty())
    {
        tmp = q.top();
        q.pop();
        if(tmp.x == ex && tmp.y == ey)
            return 1;
        for(int i = 0; i < 4; i ++)
        {
            s.x = tmp.x + d[i][0];
            s.y = tmp.y + d[i][1];
            if(f[s.x][s.y]) continue;
            if(judge(s.x, s.y) || map[s.x][s.y] == 1 || (s.x == jx && s.y == jy)) continue;//不能穿過箱子
            s.step = tmp.step + 1;
            f[s.x][s.y] = true;
            q.push(s);
        }
    }
    return 0;
}
void bfs()
{
    memset(v, -1, sizeof(v));
    priority_queue  q;
    node s, tmp;
    s.x = sx;
    s.y = sy;
    s.rx = rx;
    s.ry = ry;
    s.step = 0;
    q.push(s);
    while(!q.empty())
    {
        tmp = q.top();
        q.pop();
        if(tmp.x == ex && tmp.y == ey)
        {
            flag = true;
            printf("%d\n",tmp.step);
            return ;
        }
        for(int i = 0; i < 4; i ++)
        {
            s.x = tmp.x + d[i][0];
            s.y = tmp.y + d[i][1];
            if(v[s.x][s.y][i] == i) continue;
            if(judge(s.x, s.y) || map[s.x][s.y] == 1) continue;

            int dx = tmp.x - d[i][0];//dx,dy表示人要推箱子時站的位置
            int dy = tmp.y - d[i][1];

            if(judge(dx, dy) || map[dx][dy] == 1) continue;//判斷位置是否越界，或該位置是牆

            if(p_bfs(tmp.rx, tmp.ry, dx, dy, tmp.x, tmp.y))
            {
                s.rx = tmp.x;
                s.ry = tmp.y;
                s.step = tmp.step + 1;
                v[s.x][s.y][i] = i;
                q.push(s);
            }
        }
    }
}
int main()
{
    int T,i,j;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(i = 0; i < n; i ++)
        for(j = 0; j < m; j ++)
        {
            scanf("%d",&map[i][j]);
            if(map[i][j] == 2) sx = i, sy = j;
            else if(map[i][j] == 3) ex = i, ey = j;
            else if(map[i][j] == 4) rx = i, ry = j;
        }
        flag = 0;
        bfs();
        if(!flag) puts("-1");
    }
    return 0;
}