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

zxj015

 
 
 

日志

 
 

hdu 1242 Rescue BFS搜索  

2011-03-22 12:17:53|  分类: 搜索 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

一个二维表:
.:路
#:障碍
a:要救的人
r:去找的人(有多个)
x:门卫
找人中若遇到门卫要多花一个单位的时间
本题可以反过来做,用a去找最近的r;


#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<string.h>
#include <iostream>
using namespace std;
char map[201][201];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int visited[201][201];
int co,ro;
struct coor
{
    int x,y;
    int step;
};
queue<coor>que;
bool judge(int x,int y)
{
    if(x<0||y<0||x>=co||y>=ro||map[x][y]=='#'||visited[x][y])
    return false;
    return true;
}
bool bfs(int a,int b)
{
    int x,y,i;
    coor in,out;
    memset(visited,0,sizeof(visited));
    while(!que.empty())
    que.pop();
    in.x=a;
    in.y=b;
    in.step=0;
    que.push(in);
    while(!que.empty())
    {
        out=que.front();
        que.pop();
        if(map[out.x][out.y]=='r')
        {
            printf("%d\n",out.step);
            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.step=out.step+1;
            if(map[x][y]=='x')
            in.step++;
            que.push(in);
        }
    }
    return false;
}
            
int main()
{
    int i,a,b,j;
    while(scanf("%d%d",&co,&ro)!=EOF)
    {
        for(i=0;i<co;i++)
        scanf("%s",map[i]);
        for(i=0;i<co;i++)
        for(j=0;j<co;j++)
        if(map[i][j]=='a')
        {
            a=i;
            b=j;
        }
        if(!bfs(a,b))
        printf("Poor ANGEL has to stay in the prison all his life.\n");
    }
    return 0;
}
  评论这张
 
阅读(78)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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