HDU 1072 Nightmare(BFS)
http://acm.hdu.edu.cn/showproblem.php?pid=1072
题意:有一个N*M的迷宫,你要从起点2走到终点3,且你身上有,这个6分钟后爆炸,你在迷宫中每走一步需要1分钟,且迷宫中有重置装置(4格子),可以使得你的爆炸时间重新变为6.不过不论是你到达终点还是你到达重置装置的地方,你身上的爆炸时间一定要>=1分钟才行,要不你就失败.重置装置可以无限使用,且迷宫中为1的格子是障碍,为0的格子是空(可以走).输出你走到终点的最短时间.
分析:又是一道设计状态的BFS题目,由于题目中每个格子可能重复走(因为要去用重置装备),所以我们设计状态如下:
struct Node
{
int r, c;//当前坐标
int time;//当前还剩time分钟爆炸
intdist;//走到当前r,c,time状态所花的时间(即所走的距离)
}Q[maxn]
所以我们用dist[r][c][time](初值-1,表示该状态还没到达) 表走到状态(r,c,time)所花的最少时间(步数).
因为所有格子都是可以重复走的,但是当我重复走这个格子的时候如果具有一个更大的time值,我就可能走得更多的格子,出现不同的结果.所以time要作为状态的一维.如果剩余time更多,当然更好,但是有可能我们剩余time少的状态也可以到达终点且dist可能更少.所以time少的状态我们也不可以抛弃(即我们不能只保存time最大的那个r和c)
AC代码:
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=10000+100;
int N,M;
int sr,sc,er,ec;//起点终点坐标
int dist[10][10][10];
int map[10][10];
int dr[]={-1,1,0,0};//上下左右
int dc[]={0,0,-1,1};
struct Node
{
int r,c,time,dist;
Node(){}
Node(int r,int c,int time,int dist):r(r),c(c),time(time),dist(dist){}
}Q[maxn];
int BFS()
{
memset(dist,-1,sizeof(dist));
int front=0,tail=1;
Q[front]=Node(sr,sc,6,0);
dist[sr][sc][6]=0;
while(front<tail)
{
Node node=Q[front];
for(int d=0;d<4;d++)
{
int nr=node.r+dr[d], nc=node.c+dc[d];
if(!(nr>=0&&nr<N&&nc>=0&&nc<M) || map[nr][nc]==0) continue;//非法坐标
int ntime = map[nr][nc]==4?6: (node.time-1);
int ndist = node.dist+1;
if(dist[nr][nc][ntime]==-1 || dist[nr][nc][ntime]>ndist)
{
dist[nr][nc][ntime]=ndist;
if(ntime>1) Q[tail++]=Node(nr,nc,ntime,ndist); //错误,这里没加前面的if,ntime如果==1,它的后继的time肯定为0,没意义
if(nr==er&&nc==ec) return ndist; //不用遍历全图,这就是最短的距离
}
}
front++;
}
return -1; //错误,忘写了返回值,出现诡异错误
}
int main()
{
int T; scanf("%d",&T);
while(T--)
{
scanf("%d%d",&N,&M);
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
{
scanf("%d",&map[i][j]);
if(map[i][j]==2)
{
sr=i, sc=j;
map[i][j]=1;
}
else if(map[i][j]==3)
{
er=i, ec=j;
map[i][j]=1;
}
}
int ans=BFS();
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
hdu 3085 一道bfs题 一点值得注意的,鬼魅先走,mm与gg后走,直接模拟这个这个场景,突出时间的先后性,一秒与一秒的区别。。。这样模拟很难出错
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
HDU最全ac代码
hdu 1166线段树代码
hdu动态规划算法集锦
hdu题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
自己做的HDU ACM已经AC的题目
HDU图论题目分类