HDU 1728 逃离迷宫(BFS的优化)
这一题,有两个地方需要注意:(除了题目令人窒息的行列的x y设置)
①转弯如何判断?
需要给转弯的方向赋值。通常,我们在节点向四个方向延伸的时候,喜欢这样
int nextx[4]={0,0,-1,1};//下一个的行
int nexty[4]={1,-1,0,0};//下一个的列
for(int i=0;i<4;i++)
{
Point nextp;
nextp.x=curp.x+nextx[i];
nextp.y=curp.y+nexty[i];
/*
........
*/
}
那既然你已经定义了i,为啥不直接用i来代表转弯的方向呢?
所以,i从0到3 分别代表了 右 左 上 下。
我们从队首取出一个节点curp,由这个节点向四个方向扩展的下一个节点是nextp。
显然,nextp的上一个结点(curp) 转弯的方向lastturn 就是 i。
(人家怎么都是用dir,,,然后我想了半天不动dir是啥,,,我这理解应该是对的叭)
②MLE 怎么办?
找个数组记录一下,走到当前位置最少需要几个转弯数?
每次更新一下。如果比当前位置的转弯数大,那根本没有必要再存队列里了,对吧。
不然内存使用你会疯掉的。
你看,我各种优化,大于K了不行赶紧扔掉:
然后优化的时候还一不小心搞错了。。。
/*问题出在,,虽然已经达到转弯的最大次数,但是接下来可以直直地走到终点。
if(nextp.turn == k)
{
if(nextp.x !=endx || nextp.y !=endy)
continue;
}*/
接下来,放上自己各种参考的代码:
//HDU 1728
//AC
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
//right left up down
int nextx[4]={0,0,-1,1};
int nexty[4]={1,-1,0,0};
char mp[105][105];
int leastturn[105][105];
int k,startx,starty,endx,endy;
int m,n;
struct Point
{
int x;
int y;
int turn;
int lastturn;//上一次转弯的方向
};
void BFS(int startx,int starty)
{
queue<Point> q;
Point startp;
startp.x=startx;startp.y=starty;
startp.turn=0;
startp.lastturn=-3;
q.push(startp);
while(!q.empty())
{
Point curp=q.front();
q.pop();
//是否是终点
if(curp.x==endx && curp.y==endy && curp.turn<=k)
{
cout<<"yes"<<endl;
return ;
}
//是否超过允许的拐弯数量
if(curp.turn >k )
continue;
for(int i=0;i<4;i++)
{
Point nextp;
nextp.x=curp.x+nextx[i];
nextp.y=curp.y+nexty[i];
//在迷宫的范围内,且可以走
if(nextp.x>=1 && nextp.x<=m && nextp.y>=1 && nextp.y<=n && mp[nextp.x][nextp.y]!='*')
{
//判断有没有拐弯。跟上一次 的方向 不相同
if(curp.lastturn !=i && curp.lastturn !=-3 )//拐弯了
{
nextp.turn=curp.turn+1;
nextp.lastturn=i;
if(nextp.turn > k)
continue;
/*问题出在,,虽然已经达到转弯的最大次数,但是接下来可以直直地走到终点。
if(nextp.turn == k)
{
if(nextp.x !=endx || nextp.y !=endy)
continue;
}*/
if(nextp.turn <= leastturn[nextp.x][nextp.y])
{
leastturn[nextp.x][nextp.y]=nextp.turn;
q.push(nextp);
}
}
else
{
nextp.turn=curp.turn;
nextp.lastturn=i;
if(nextp.turn > k)
continue;
/* if(nextp.turn == k)
{
if(nextp.x !=endx || nextp.y !=endy)
continue;
}*/
if(nextp.turn <= leastturn[nextp.x][nextp.y])
{
leastturn[nextp.x][nextp.y]=nextp.turn;
q.push(nextp);
}
}
}
}
}
cout<<"no"<<endl;
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>m>>n;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
cin>>mp[i][j];
leastturn[i][j]=INT_MAX;
}
}
cin>>k>>starty>>startx>>endy>>endx;
BFS(startx,starty);
}
}