HDU 2612 Find a way(简单BFS)
http://acm.hdu.edu.cn/showproblem.php?pid=2612
题意:给你一个N*M的迷宫,现在给你A和B的初始坐标,他们要在’@’点集合(迷宫可能有多个’@’点),问你他们集合的最少时间是多少.
分析:直接从A和B的初始坐标分别做两次BFS即可,然后对于每个’@’点,算出A和B分别到’@’的距离,相加即可.
注意:如果我们最后算的的dist[1][r][c]==-1,那么表示这点是不可到达的,不能用来算最短ans.我在这里找了好久BUG.
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=200+10;
int dr[]={-1,1,0,0};//上下左右
int dc[]={0,0,-1,1};
struct Node
{
int r,c;
Node(){}
Node(int r,int c):r(r),c(c){}
};
int R,C;//迷宫规模
int sr,sc,er,ec;//A点与B点坐标
char map[maxn][maxn];
int dist[2][maxn][maxn];
void BFS(int r,int c,int type)
{
memset(dist[type],-1,sizeof(dist[type]));
queue<Node> Q;
Q.push(Node(r,c));
dist[type][r][c]=0;
while(!Q.empty())
{
Node node=Q.front(); Q.pop();
for(int d=0;d<4;d++)
{
int nr=node.r+dr[d], nc=node.c+dc[d];
if(nr>=0&&nr<R&&nc>=0&&nc<C&&map[nr][nc]!='#'&&dist[type][nr][nc]==-1)
{
dist[type][nr][nc]=dist[type][node.r][node.c]+1;
Q.push(Node(nr,nc));
}
}
}
}
int main()
{
while(scanf("%d%d",&R,&C)==2)
{
vector<Node> KFC;//记录每个KFC
for(int i=0;i<R;i++)
for(int j=0;j<C;j++)
{
scanf(" %c",&map[i][j]);
if(map[i][j]=='Y') sr=i, sc=j; //A点坐标
else if(map[i][j]=='M') er=i, ec=j; //B点坐标
else if(map[i][j]=='@') KFC.push_back(Node(i,j)); //KFC坐标
}
BFS(sr,sc,0);
BFS(er,ec,1);
int min=1e8;
for(int i=0;i<KFC.size();i++)
{
int len1=dist[0][KFC[i].r][KFC[i].c], len2=dist[1][KFC[i].r][KFC[i].c];
if(len1==-1 || len2==-1) continue; //错误, 忘写这句话,导致一直WA
int length = len1+len2 ;
if(min>length) min=length;
}
printf("%d\n",min*11);
}
return 0;
}
分享到:
相关推荐
hdu 3085 一道bfs题 一点值得注意的,鬼魅先走,mm与gg后走,直接模拟这个这个场景,突出时间的先后性,一秒与一秒的区别。。。这样模拟很难出错
现在,给你两个正的小数A和B,你的任务是代表大明计算出A+B的值。 Input 本题目包含多组测试数据,请处理到文件结束。 每一组测试数据在一行里面包含两个长度不大于400的正小数A和B。 Output 请在一行里面...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu ACM 各种排序
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu_2102_passed_sorce
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 1005.比较简单的一道题,有兴趣的可以看看。
hdu1290 解题报告 献给杭电五十周年校庆的礼物 (切西瓜问题,即平面分割空间)
hdu 1166线段树代码
ACM HDU题目分类,我自己总结的大概只有十来个吧