推箱子 BFS

#include <bits/stdc++.h>
using namespace std;
int n,m,sx,sy,bx,by,ex,ey;
int dir[4][2]={{-1,0},{0,1},{0,-1},{1,0}};
const int maxn=10;
int vis[maxn][maxn][maxn][maxn];
char str[maxn][maxn];
struct edge{
    int sx,sy,bx,by,step;
    edge(int sx,int sy,int bx,int by,int step):
        sx(sx),sy(sy),bx(bx),by(by),step(step){}
    friend bool operator < (edge x,edge y)
    {
        return x.step>y.step;//小的先出 同greater
    }
};
bool check(int x,int y,int bx,int by)
{
    if(vis[x][y][bx][by]) return 1;
    if(x<0||x>=n||y<0||y>=m||str[x][y]==‘#‘) return 1;
    if(bx<0||bx>=n||by<0||by>=m||str[bx][by]==‘#‘) return 1;
    return 0;
}
void bfs()
{
    priority_queue<edge> q;
    edge c(sx,sy,bx,by,0);
    memset(vis,0,sizeof(vis));
    vis[sx][sy][bx][by]=1; q.push(c);
    while(!q.empty()){
        c=q.top();q.pop();
        if(c.bx==ex&&c.by==ey){
            printf("%d\n",c.step);
            return ;
        }
        for(int i=0;i<4;i++){
            int x=c.sx+dir[i][0],y=c.sy+dir[i][1];
            if(check(x,y,c.bx,c.by)) continue;
            //这里不能先标记 因为推箱子可能从四个方向推过来的
            if(x==c.bx&&y==c.by){ //碰到箱子
                int tx=c.bx+dir[i][0];
                int ty=c.by+dir[i][1];
                if(check(x,y,tx,ty)) continue;
                vis[x][y][tx][ty]=1;
                edge ne(x,y,tx,ty,c.step+1);
                q.push(ne);
            }
            else{//没碰到箱子
                edge ne(x,y,c.bx,c.by,c.step+1);
                vis[x][y][c.bx][c.by]=1;
                q.push(ne);
            }
        }
    }
    puts("-1");
    return ;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i=0;i<n;i++) scanf("%s",str[i]);
        for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            if(str[i][j]==‘X‘) sx=i,sy=j;
            if(str[i][j]==‘@‘) ex=i,ey=j;
            if(str[i][j]==‘*‘) bx=i,by=j;
        }
        bfs();
    }
    return 0;
}