注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zxj015

 
 
 

日志

 
 

poj 2312 Battle City 优先队列+bfs 或 记忆化广搜  

2011-04-11 21:34:18|  分类: 搜索 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

http://poj.org/problem?id=2312
    相信坦克大战大家都玩过吧,本题就是根据这个游戏设计的。坦克要从起点(Y),到目的地(T),坦克不能通过钢墙(S),河(R),可以在空地在行走(E),射击破坏砖墙(B),射击砖墙时不行走且花费一个单位的时间。求坦克从起点到目的地最少花多少时间,不可达输出-1;
    很好的一道搜索题。因为考虑到通过砖墙时和空地所花的时间不同,所以不能简单的用BFS广搜来做。用DFS深搜,你会发现时间复杂非常高,必然会超时(最大是300*300的图)。本题可以能过优先队列+bfs 或 记忆化广搜两种方法来解决。
一、优先队列+BFS法:
     也是用到了广搜的思想,只是在出队时做了处理,利用优先队列让队列中到起点的时间值最小的点先出队。该方法会用到优先队列的STL。
二、记忆化广搜
     和优先队列BFS在出队时做处理不同的是,记忆化广搜是在点入队是做处理。记忆化广搜时不必要对点进行标记,只是在入队是注意选择。比如若搜到A点时,要选择比A点时间值大的邻接点入队(不能相等),并更新入队点的时间值。

优先队列+BFS法代码:
#include<stdio.h>
#include<stdlib.h>
#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}};
struct coor
{
        int x;
        int y;
        int time;
};
bool operator < (const coor &a, const coor &b)
{
    return a.time > b.time; //从小到大排序
}
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'||visited[x][y])
        {
               
                return false;
        }
       
        return true;
}
bool bfs(int a,int b)
{
        int i,x,y,ti;
        coor in,out;
        priority_queue<coor>que;
        in.x=a;
        in.y=b;
        in.time=0;
        que.push(in);
        while(!que.empty())
        {
                out=que.top();
                que.pop();
                if(map[out.x][out.y]=='T')
                {
                        printf("%d\n",out.time);
                        return true;
                }  
                for(i=0;i<4;i++)
                {
                        x=out.x+dir[i][0];
                        y=out.y+dir[i][1];
                        if(!judge(x,y))
                                continue;
                        visited[x][y]=1;
                        in.x=x;
                        in.y=y;
                        in.time=out.time+1;
                        if(map[x][y]=='B')
                                in.time++;                       
                        que.push(in);
                }
        }
        return false;
}
               
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;
                        }    
                }
               
                memset(visited,0,sizeof(visited));
                visited[a][b]=1;
                if(!bfs(a,b))
                        printf("-1\n");
           
        }
        return 0;
}

记忆化广搜代码:
#include<stdio.h>
#include<stdlib.h>
#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;
        struct node *next;
}coor;
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;
        coor in,out;
        queue<coor>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;
}
  评论这张
 
阅读(182)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018