「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';
}
}
尾声
如果你发现了问题,你可以直接回复这篇题解
如果你有更好的想法,也可以直接回复!
标签:箱子,题解,ll,Pushing,Boxes,continue,czc,push,maze From: https://www.cnblogs.com/zsc985246/p/16621280.html