当前位置：首页 > article >正文

[leetcode]1263. 推箱子(A*+优先队列BFS+DFS)

article 2025/3/25 17:19:48

题目链接

题意

给定 $n\times m$ 的地图
'.'可以走 '#'是墙
'S’是玩家初始位置 'B’是箱子初始位置 'T’是箱子目标位置

求箱子的最小推动次数
不是人走的步数人可以走任意步数每次推箱子要走到箱子移动方向的另一头如果此时没有路能到这个点就不能推

数据范围 $1\leq n,m\leq 20$

思路

思路来自题解
不过他是java写的我改成了c++

数据很小显然BFS

这题有一个要特别注意的点箱子也占一格可能会把人挡住所以不能一开始就用并查集预处理空白点的联通性要动态判断两点间的联通性

由于数据范围很小所以可以用dfs判断联通性

Code

#define pii pair<int,int>
#define ar2 array<int,2>
#define ar3 array<int,3>
#define ar4 array<int,4>
#define ar5 array<int,5>
#define endl '\n'
void cmax(int &a,int b){a=max(a,b);};
void cmin(int &a,int b){a=min(a,b);};
const int N=2e5+10,MOD=1e9+7,INF=0x3f3f3f3f;const long long LINF=LLONG_MAX;const double eps=1e-6;
vector<vector<char>>g;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};

//仿函数自定义优先队列排序方式：按照第二个元素推动次数排序的小根堆
struct cmp{
    bool operator()(const ar5&a,const ar5&b){
        return a[2]>b[2];
    }
};

class Solution {
public:
    int n,m;
    ar2 box,target,player;
    int minPushBox(vector<vector<char>>& grid) {
        g=grid;
        n=grid.size(),m=grid[0].size();

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                char &c=g[i][j];
                if(c=='B') {
                    box={i,j};
                    c='.';
                }else if(c=='T'){
                    target={i,j};
                    c='.';
                }else if(c=='S'){
                    player={i,j};
                    c='.';
                }
            }
        }
//BFS部分
-------------------------------------------------------
        vector<vector<bool>>flags(n*m,vector<bool>(n*m));
        priority_queue<ar5,vector<ar5>,cmp>pq;

        //预处理 把箱子四联通相邻的点中 人能到达的点都入队
        g[box[0]][box[1]]='#';
        for(int i=0;i<4;i++){
            int tx=box[0]+dx[i],ty=box[1]+dy[i];
            if(tx<0||tx>=n||ty<0||ty>=m||g[tx][ty]=='#')continue;
            vector<bool>vis(n*m);
            if(dfs(player[0],player[1],tx,ty,vis)){
                flags[index(box[0],box[1])][index(tx,ty)]=1;
                pq.push({box[0],box[1],0,tx,ty});
            }
        }
        g[box[0]][box[1]]='.';

        //BFS
        while(pq.size()){
            auto [x,y,cnt,px,py]=pq.top();pq.pop();
            if(x==target[0]&&y==target[1]) return cnt;
            
            for(int i=0;i<4;i++){
                int tx=x+dx[i],ty=y+dy[i];
                int opp=(i+2)%4;//箱子移动的反方向是玩家要去的点
                int ox=x+dx[opp],oy=y+dy[opp];
                if(tx<0||tx>=n||ty<0||ty>=m||g[tx][ty]=='#'||flags[index(tx,ty)][index(px,py)]) continue;
                if(ox<0||ox>=n||oy<0||oy>=m||g[ox][oy]=='#') continue;

                vector<bool>vis(n*m);
                g[x][y]='#';
                if(dfs(px,py,ox,oy,vis)){
                    flags[index(tx,ty)][index(px,py)]=1;
                    pq.push({tx,ty,cnt+1,x,y});
                }
                g[x][y]='.';
            }
            
        }

        return -1;
    }
//dfs函数 判断(x,y)到(ex,ey)联通性
//vis数组在dfs外面建好作为参数传进来,不能在dfs内部开vis数组 因为dfs要递归调用的
---------------------------------------------------------
    bool dfs(int x,int y,int ex,int ey,vector<bool>&vis){
        if(x==ex&&y==ey) return 1;

        for(int i=0;i<4;i++){
            int tx=x+dx[i],ty=y+dy[i];
            if(tx<0||tx>=n||ty<0||ty>=m||g[tx][ty]=='#'||vis[index(tx,ty)]) continue;

            vis[index(tx,ty)]=1;
            if(dfs(tx,ty,ex,ey,vis)) return 1;
        }

        return 0;
    }
//状态压缩成一维坐标
--------------------------------------------------------
    int index(int i,int j){
        return i*m+j;
    }

};