优先队列 深入讨论POJ 2312 Battle City 优先队列+BFS
人气:0想了解深入讨论POJ 2312 Battle City 优先队列+BFS的相关内容吗,在本文为您仔细讲解优先队列的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:优先队列,下面大家一起来学习吧。
相信坦克大战大家都玩过吧,本题就是根据这个游戏设计的。坦克要从起点(Y),到目的地(T),坦克不能通过钢墙(S),河(R),可以在空地在行走(E),射击破坏砖墙(B),射击砖墙时不行走且花费一个单位的时间,在空地上行走时也花费一个单位的时间。求坦克从起点到目的地最少花多少时间,不可达输出-1;很好的一道搜索题。因为考虑到通过砖墙时和空地所花的时间不同,所以不能使用一般的BFS广搜来做。用DFS深搜,你会发现时间复杂非常高,必然会超时(最大是300*300的图)。本题可以使用改进过的广搜或优先队列+bfs 或 记忆化广搜三种方法来解决。
第一种方法:改进过的BFS:
有些节点需要耗费2个单位时间,要想用BFS就得改一下,由于BFS每次只能操作一步,要不就是扩展,要不就是破坏砖墙。所以只需检查该点是不是'B',是的话就得停一步,不是的话,继续扩展,也就是说某些点的扩展慢了一拍,所以从队列里出来的点就判断一下再看执行哪个操作。
从这道题,我也对bfs有了更深的理解,“bfs之所以能最快找到最优解,就是因为它每次操作一步(这里的操作一步,很灵活,例如题目中的破坏砖墙),而while()里面的语句就是一次操作了!”
复制代码 代码如下:
/*
这道题中B点需要操作两步,所以遇到B点后不能+2后直接压进队列,需要在原地停一下,不能扩展到其他点,相当于他只能扩展到自身,所以就把自身压进队列里map[x][y]='E'是因为破坏砖墙一次就够了,不然下次,还是'B',不断压进队列,不断在原地停留
平常一般是考虑“入队列” 的点,这次要考虑“出队列” 的点是否满足条件!
*/
#include "iostream"
#include "queue"
using namespace std;
char map[301][301];
bool visit[301][301];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int m,n,sx,sy;
struct node
{
int x,y,time;
};
int bfs()
{
int i;
node you,start,next;
queue<node>q;
you.x=sx;
you.y=sy;
you.time=0;
q.push(you);
visit[sx][sy]=1;
while(!q.empty())
{
start=q.front();
q.pop();
if(map[start.x][start.y]=='B') //这一步需要停一停
{
start.time++;
map[start.x][start.y]='E';
q.push(start);
}
else
{
for(i=0;i<4;i++)
{
next.x=start.x+dir[i][0]; //搜索下一个点
next.y=start.y+dir[i][1];
if(next.x<0 || next.y<0 || next.x>=m || next.y>=n || map[next.x][next.y]=='R' || map[next.x][next.y]=='S' || visit[next.x][next.y]) //判断下一个点是否合法
continue;
next.time=start.time+1;
if(map[next.x][next.y]=='T') //到达目的地
return next.time;
visit[next.x][next.y]=1; //标记已经走过的点
q.push(next);
}
}
}
return -1;
}
int main(void)
{
int i,j;
while(scanf("%d %d",&m,&n)==2)
{
if(m==0 && n==0)
break;
memset(visit,0,sizeof(visit)); //初始化每个节点的状态
for(i=0;i<m;i++)
{
getchar();
for(j=0;j<n;j++)
{
scanf("%c",&map[i][j]);
if(map[i][j]=='Y') //记录起始点
{
sx=i;
sy=j;
}
}
}
printf("%d\n",bfs());
}
system("pause");
return 0;
}
第二种方法:优先队列+BFS法
也是用到了广搜的思想,只是在出队时做了处理,利用优先队列让队列中到起点的时间值最小的点先出队。该方法会用到优先队列的STL。
首先需要了解优先队列的使用规则:
优先队列中元素的比较规则默认是按元素的值从大到小排序的,就是说队列中最大的元素总是位于队首,所以出队时,并非按先进先出的原则进行,而是将当前队列中最大的元素出队。这点类似于给队列里的元素进行了从大到小的排序。当然,可以通过重载“<”操作符来重新定义比较规则。
重载“<”操作符的函数可以写在结构体里面,也可以写在结构体外面,写在结构体外面的时候,记得函数的参数要使用引用。。
第一种重载方法:
复制代码 代码如下:
struct node
{
int x,y;
int step;
};
priority_queue<node>q; //优先队列中元素的比较规则默认是按元素的值从大到小排序;
bool operator<(const node &a,const node &b) //括号里面是const 而且还必须是引用
{
return a.step>b.step; //从小到大排序。重载小于号。因为默认是从大到小
}
第二种重载方法:
复制代码 代码如下:
struct node
{
int x,y;
int time; //定义一个优先队列
friend bool operator<(node a, node b)
{ //从小到大排序采用“>”号;如果要从大到小排序,则采用“<”号
return a.time> b.time; //从小到大排序
}
};
priority_queue<node>q; //优先队列中元素的比较规则默认是按元素的值从大到小排序;
切记:从小到大排序采用“>”号;如果要从大到小排序,则采用“<”号;
复制代码 代码如下:
/*
优先队列的实现就不用局限每次操作一步了,但每次都取最小操作次数的步来走
*/
#include "iostream"
#include "queue"
using namespace std;
char map[301][301];
bool visit[301][301];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int m,n,sx,sy;
struct node
{
int x,y,time; //定义一个优先队列
friend bool operator<(node a, node b)
{
return a.time> b.time; //从小到大排序
}
};
int bfs()
{
int i;
node you,start,next;
priority_queue<node>q;
you.x=sx;
you.y=sy;
you.time=0;
q.push(you);
visit[sx][sy]=1;
while(!q.empty())
{
start=q.top(); //取队头指针与普通队列不同(Q.front)
q.pop();
for(i=0;i<4;i++)
{
next.x=start.x+dir[i][0]; //搜索下一个点
next.y=start.y+dir[i][1];
if(next.x<0 || next.y<0 || next.x>=m || next.y>=n || map[next.x][next.y]=='R' || map[next.x][next.y]=='S' || visit[next.x][next.y]) //判断下一个点是否合法
continue;
if(map[next.x][next.y]=='B') //注意此处不要马虎
next.time=start.time+2;
else
next.time=start.time+1;
if(map[next.x][next.y]=='T') //到达目的地
return next.time;
visit[next.x][next.y]=1; //标记已经走过的点
q.push(next);
}
}
return -1;
}
int main(void)
{
int i,j;
while(scanf("%d %d",&m,&n)==2)
{
if(m==0 && n==0)
break;
memset(visit,0,sizeof(visit)); //初始化每个节点的状态
for(i=0;i<m;i++)
{
getchar();
for(j=0;j<n;j++)
{
scanf("%c",&map[i][j]);
if(map[i][j]=='Y') //记录起始点
{
sx=i;
sy=j;
}
}
}
printf("%d\n",bfs());
}
system("pause");
return 0;
}
第三种方法:记忆化广搜
和优先队列BFS在出队时做处理不同的是,记忆化广搜是在点入队是做处理。记忆化广搜时不必要对点进行标记,只是在入队是注意选择。比如若搜到A点时,要选择比A点时间值大的邻接点入队(不能相等),并更新入队点的时间值。
复制代码 代码如下:
#include<string.h>
#include<iostream>
#include<queue>
using namespace std;
int co,ro,mi,step[305][305];
char map[305][305],visited[305][305];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
typedef struct node
{
int x;
int y;
int time;
}node;
bool judge(int x,int y)
{
if(x<0||y<0||x>=co||y>=ro)
{
return false;
}
if(map[x][y]=='S'||map[x][y]=='R')
{
return false;
}
return true;
}
void bfs(int a,int b)
{
int i,x,y,ti;
node in,out;
queue<node>que;
in.x=a;
in.y=b;
step[a][b]=0;
que.push(in);
while(!que.empty())
{
out=que.front();
que.pop();
visited[out.x][out.y]=0;
for(i=0;i<4;i++)
{
x=out.x+dir[i][0];
y=out.y+dir[i][1];
if(!judge(x,y))
continue;
ti=step[out.x][out.y]+1;
if(map[x][y]=='B')
ti++;
if(step[x][y]<=ti)
continue;
step[x][y]=ti;
if(visited[x][y])
continue;
visited[x][y]=1;
in.x=x;
in.y=y;
que.push(in);
}
}
}
int main()
{
int i,j,a,b,c,d;
while(scanf("%d %d",&co,&ro),co+ro)
{
getchar();
for(i=0;i<co;i++)
gets(map[i]);
for(i=0;i<co;i++)
for(j=0;j<ro;j++)
{
if(map[i][j]=='Y')
{
a=i;
b=j;
}
if(map[i][j]=='T')
{
c=i;
d=j;
}
step[i][j]=999999;
}
memset(visited,0,sizeof(visited));
visited[a][b]=1;
bfs(a,b);
if(step[c][d]!=999999)
printf("%d\n",step[c][d]);
else
printf("-1\n");
}
return 0;
}
加载全部内容