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

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 1072  

2012-03-25 19:12:35|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

http://acm.hdu.edu.cn/showproblem.php?pid=1072

题意:I想(从2处)逃出迷宫(3处),0是墙,1是空地。身上有定时炸弹,在第6s爆炸(只能走5步)。4处是将定时炸弹重设的对象(即剩下的时间又归为6秒)。问它最快可否逃出迷宫。

BFS,需要设一个二维数组记录剩余时间;

注意:如果搜到某个点时所剩的时间大于等于该点记录的时间,则还可以把这个点加到队列里

#include<iostream>
#include<math.h>
#include<string.h>
#include<queue>
#include<string>
#include<algorithm>
#include<stdio.h>
using namespace std;
#define N 10
typedef struct Node
{
    int x,y;
}Point;
Point s,e;
int n,m;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int map[N][N],dis[N][N],a[N][N];

int BFS()
{
    int i;
    Point b,t;
    queue<Point> Q;
    dis[s.x][s.y]=0;
    a[s.x][s.y]=5;
    Q.push(s);
    while(!Q.empty())
    {
        t=Q.front();
        Q.pop();
        for(i=0;i<4;i++)
        {
            b.x=t.x+dir[i][0];
            b.y=t.y+dir[i][1];
            if(b.x>=0 && b.x<n && b.y>=0 && b.y<=m && a[t.x][t.y]-1 >= a[b.x][b.y] &&map[b.x][b.y]!=0)
            {
                dis[b.x][b.y]=dis[t.x][t.y]+1;
                if(map[b.x][b.y]==3)
                    return dis[b.x][b.y];

    a[b.x][b.y]=a[t.x][t.y]-1;
                if(map[b.x][b.y]==4)
                    a[b.x][b.y]=5;
    if(a[b.x][b.y]==0)
     continue;
                Q.push(b);
            }
        }
    }
 return -1;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("testin.txt","r",stdin);
 //freopen("testout.txt","w",stdout);
#endif
    int T,i,j;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&n,&m);
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                scanf("%d",&map[i][j]);
                if(map[i][j]==2)
                {
                    s.x=i;
                    s.y=j;
                }
            }
        }
        memset(dis,-1,sizeof(dis));
        memset(a,0,sizeof(a));
        printf("%d\n",BFS());
    }
    return 0;
}

  评论这张
 
阅读(186)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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