「POJ1475」Pushing Boxes 题解

题目大意

一张N行M列的地图，字符“.”表示空地，字符“#”表示墙，字符“S”表示人的起始位置，字符“B”表示箱子的起始位置，字符“T”表示箱子的目标位置。

求一种移动方案，使箱子移动的次数最少，在此基础上再让人移动的总步数最少。方案中使用大写的“EWSN”表示箱子的推动，使用小写的“ewsn”表示人的移动。N,M<=20。

输入

两个整数N和M，表示行数和列数。

接下来N行，每行M个字符，表示迷宫。

输入以0 0结束。

输出

首先输出迷宫的编号。

如果无法完成任务，输出“Impossible.”，否则，输出一个最小化推送次数的序列。

在每个测试用例后输出一个空白行。

思路

初始思路

看到数据范围，首先考虑搜索。

为了提高效率，考虑 A_star。

分析题目，“使箱子移动的次数最少，在此基础上再让人移动的总步数最少”，所以我们用迭代加深的思想。

下面是$ TLE $的IDA_star（BFS的IDA_star？？？）：

#include<bits/stdc++.h>
#define ll long long
const ll N=50010;
using namespace std;

struct node{
    ll maze[21][21];//地图 
    ll h;//估价值 
    ll step;//走过的步数 
    ll cnt;//推了多少次箱子 
    string s;//答案字符串 
    bool operator < (const node&other)const{//重载运算符 
        step+h>other.step+other.h;
    }
}a[N],s;//a为中间状态，s为起始状态 
ll n,m,tx,ty;//地图大小 
ll nt[4][2]={0,1,1,0,0,-1,-1,0};//方向 
char ntc[4]={'e','s','w' ,'n' };

ll h(node x){//估价函数 
    ll sx,sy;//箱子的坐标 
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            if(x.maze[i][j]==2){
                sx=i,sy=j;
            }
        }
    }
    return abs(sx-tx)+abs(sy-ty);//箱子到终点的距离 
}

bool A_star(ll limit){//limit是步数限制 
    priority_queue<node>q;
    unordered_map<ll,ll>vis;
    q.push(s);
    while(!q.empty()){
        node p=q.top();
        q.pop();
        ll num=0,x,y;
        //你的坐标 
        for(ll i=1;i<=n;i++){
            for(ll j=1;j<=m;j++){
                if(p.maze[i][j]==1){
                    num=num*100+i;
                    num=num*100+j;
                    x=i;
                    y=j;
                }
            }
        }
        //箱子的坐标 
        for(ll i=1;i<=n;i++){
            for(ll j=1;j<=m;j++){
                if(p.maze[i][j]==2){
                    num=num*100+i;
                    num=num*100+j;
                }
            }
        }
        if(vis[num])continue;
        vis[num]=1;//打标记 
        if(p.h==0){//到终点了 
            cout<<p.s<<'\n';//输出答案字符串 
            return true;
        }
        for(ll i=0;i<4;i++){
            ll nxt_x=x+nt[i][0],nxt_y=y+nt[i][1];//你下一步的坐标 
            if(nxt_x<1||nxt_x>n||nxt_y<1||nxt_y>m)continue;//第一道关：边界 
            if(p.maze[nxt_x][nxt_y]==3)continue;//第二道关：障碍 
            node czc=p;//下一步状态 
            if(czc.maze[nxt_x][nxt_y]==2){//你下一步的坐标有箱子 
                if(czc.maze[nxt_x+nt[i][0]][nxt_y+nt[i][1]]==3){//第三道关：箱子遇到障碍 
                    continue;
                }
                swap(czc.maze[nxt_x][nxt_y],czc.maze[nxt_x+nt[i][0]][nxt_y+nt[i][1]]);//推箱子 
                czc.s+=ntc[i]-32;//大写 
                czc.cnt++;//推箱子次数加一 
            }else czc.s+=ntc[i];//小写 
            swap(czc.maze[x][y],czc.maze[nxt_x][nxt_y]);//走一步 
            czc.step++;//步数加一 
            czc.h=h(czc);//估价 
            if(czc.cnt>limit)continue;//最后一道关：推箱子次数限制 
            q.push(czc);//成功通关，加入堆中 
        }
    }
    return false;
}

int main(){

    ll cnt=0;
    while(cin>>n>>m){
        cnt++;
        if(n==0&&m==0)return 0;
        for(ll i=1;i<=n;i++){
            for(ll j=1;j<=m;j++){
                char c;
                cin>>c;
                if(c=='#')s.maze[i][j]=3;//障碍 
                if(c=='.')s.maze[i][j]=0;//路面 
                if(c=='S')s.maze[i][j]=1;//你的位置 
                if(c=='B')s.maze[i][j]=2;//箱子 
                if(c=='T')s.maze[i][j]=0,tx=i,ty=j;//终点 
            }
        }
        s.h=h(s);
        cout<<"Maze #"<<cnt<<'\n';//测试点信息 
        ll i=1;
        for(;!A_star(i)&&i<=2*n*m;i++);//IDA* 
        if(i>2*n*m)cout<<"Impossible.\n";//不可能 
        cout<<'\n';
    }

    return 0;
}

TLE？

Q：如何解决？

重构+转换思想

A：既然要推箱子，那BFS箱子就可以了。

Q：人推不到怎么办？

A：再来一个BFS。这个BFS枚举人能到达的点，如果可以到达推箱子的点，就返回true，否则返回false。

Q：那最后如何输出？

A：在第二个BFS里记录到达推箱子的点的路径，最后拼接到一起。

代码实现

IDBFS（？？？）代码如下（差点心肌梗塞，所以变量名很奇怪）

#include<bits/stdc++.h>
#define ll int
using namespace std;


ll n,m;//地图大小 
ll sx,sy,bx,by,tx,ty;//三个特殊位置 
ll maze[21][21];//地图 
string S;//寄存答案 
ll nt[4][2]={-1,0,1,0,0,1,0,-1};//方向 
char ntc[4]={'n' ,'s','e','w' };//对应的字母 

bool push_bfs(ll SX,ll SY,ll X,ll Y,ll ex,ll ey){//你能否到达推箱子的位置 
    //SX,SY为你的坐标，X,Y为箱子的坐标，ex,ey为推箱子的位置 

    queue<ll>qx,qy;//qx为x坐标，qy为y坐标 
    queue<string>qs;//答案字符串 
    ll vis[21][21]={};//标记 
    qx.push(SX),qy.push(SY),qs.push("");//初始状态 
    vis[SX][SY]=1;//打标记 
    while(!qx.empty()){
        ll x=qx.front(),y=qy.front();//当前坐标 
        string s=qs.front();//当前行走状态 
        qx.pop(),qy.pop(),qs.pop();//出队 
        if(x==ex&&y==ey){//到达目标点 
            sx=x,sy=y,S=s;//记录你现在的位置及行走状态 
            return true;
        }
        for(ll i=0;i<4;i++){//四个方向 
            ll xx=x+nt[i][0],yy=y+nt[i][1];//下一个位置的坐标 
            if(xx<1||xx>n||yy<1||yy>m)continue;//出界 
            if(vis[xx][yy])continue;//被标记过 
            if(maze[xx][yy]==3)continue;//障碍 
            if(xx==X&&yy==Y)continue;//箱子 
            vis[xx][yy]=1;//打标记 
            qx.push(xx),qy.push(yy),qs.push(s+ntc[i]);//入队 
        }
    }
    return false;

} 

bool box_bfs(ll limit){

    queue<ll>qx,qy,qt,Qx,Qy;//qx为x坐标，qy为y坐标,Qx为你的x坐标，Qy为你的y坐标 
    queue<string>qs;//答案字符串 
    ll vis[21][21]={};//标记 
    qx.push(bx),qy.push(by),qt.push(0),Qx.push(sx),Qy.push(sy),qs.push("");//初始状态 
    vis[bx][by]=1;//打标记 
    while(!qx.empty()){
        ll x=qx.front(),y=qy.front(),t=qt.front(),X=Qx.front(),Y=Qy.front();//当前坐标 
        string s=qs.front();//当前行走状态 
        qx.pop(),qy.pop(),qs.pop(),Qx.pop(),Qy.pop();//出队 
        if(t>limit)continue;
        if(x==tx&&y==ty){
            cout<<s<<'\n';
            return true;
        }
        for(ll i=0;i<4;i++){//四个方向 
            ll xx=x+nt[i][0],yy=y+nt[i][1];//下一个位置的坐标 
            string ss=s;//下一个答案字符串 
            if(xx<1||xx>n||yy<1||yy>m)continue;//出界 
            if(vis[xx][yy])continue;//被标记过 
            if(maze[xx][yy]==3)continue;//障碍 
            if(!push_bfs(X,Y,x,y,x-nt[i][0],y-nt[i][1]))continue;//无法到达推箱子的位置 
            ss+=S;
            ss+=ntc[i]-32;
            sx=x,sy=y;
            vis[xx][yy]=1;//打标记 
            qx.push(xx),qy.push(yy),qt.push(t+1),Qx.push(sx),Qy.push(sy),qs.push(ss);//入队 
        }
    }
    return false;

}

int main(){

    ll cnt=0;
    while(cin>>n>>m){
        cnt++;
        if(n==0&&m==0)return 0;
        for(ll i=1;i<=n;i++){
            for(ll j=1;j<=m;j++){
                char c;
                cin>>c;
                if(c=='#')maze[i][j]=3;//障碍 
                if(c=='.')maze[i][j]=0;//路面 
                if(c=='S')maze[i][j]=1,sx=i,sy=j;//你的位置 
                if(c=='B')maze[i][j]=2,bx=i,by=j;//箱子 
                if(c=='T')maze[i][j]=0,tx=i,ty=j;//终点 
            }
        }
        cout<<"Maze #"<<cnt<<'\n';//格式 
        ll i;
        for(i=1;!box_bfs(i)&&i<=n*m;i++);//迭代加深 
        if(i==n*m+1)cout<<"Impossible.\n";//不可能 
        cout<<'\n';
    }

}

尾声

如果你发现了问题，你可以直接回复这篇题解

如果你有更好的想法，也可以直接回复！