博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[ACM] hdu Find a way
阅读量:6500 次
发布时间:2019-06-24

本文共 4373 字,大约阅读时间需要 14 分钟。

Find a way

                                                               Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
                                                                                  Total Submission(s): 3238    Accepted Submission(s): 1051


Problem Description
Pass a year learning in Hangzhou, yifenfei arrival hometown Ningbo at finally. Leave Ningbo one year, yifenfei have many people to meet. Especially a good friend Merceki.
Yifenfei’s home is at the countryside, but Merceki’s home is in the center of city. So yifenfei made arrangements with Merceki to meet at a KFC. There are many KFC in Ningbo, they want to choose one that let the total time to it be most smallest. 
Now give you a Ningbo map, Both yifenfei and Merceki can move up, down ,left, right to the adjacent road by cost 11 minutes.
 

Input
The input contains multiple test cases.
Each test case include, first two integers n, m. (2<=n,m<=200). 
Next n lines, each line included m character.
‘Y’ express yifenfei initial position.
‘M’    express Merceki initial position.
‘#’ forbid road;
‘.’ Road.
‘@’ KCF
 

Output
For each test case output the minimum total time that both yifenfei and Merceki to arrival one of KFC.You may sure there is always have a KFC that can let them meet.
 

Sample Input
 
4 4 Y.#@ .... .#.. @..M 4 4 Y.#@ .... .#.. @#.M 5 5 Y..@. .#... .#... @..M. #...#
 

Sample Output
 
66 88 66
 

Author
yifenfei
 

Source

解题思路:这道题属于简单的入门级bfs,由于昨天被某一bfs题虐了半天,这道题做起来感觉很好,写下来一气呵成,bfs框架也差不多印在脑子里了。题目两个人到KFC见面,两个人在不同的位置,KFC也不只一个,对每个人BFS广搜,求出每个人到各个KFC的最短距离,最后对于多个KFC地点,求出两个人到这的最小步数的和,取最小值就可以了。

代码:(该代码错误!虽然能提交通过,但是代码是错的!下面已经改正,并附上了正确代码)

#include 
#include
#include
#include
using namespace std;char map[202][202];//地图int a[202][202];//保存第一个人Y到各个节点(坐标)的最小步数,有的节点不用访问,下面有说明int b[202][202];//保存第二个人M int dx[4]={0,0,-1,1};int dy[4]={1,-1,0,0};//方向int n,m;//地图大小int kcount;//KFC一共的个数int yx,yy,mx,my;//Y的坐标,M的坐标int flag;//用来判断执行第一个人的BFS还是第二个人的BFSvoid getmap()//输入地图{ for(int i=0;i
>map[i][j]; if(map[i][j]=='@') kcount++; else if(map[i][j]=='Y') { yx=i; yy=j; } else if(map[i][j]=='M') { mx=i; my=j; } }}struct node{ int x,y;};void bfs(int x,int y){ int k=0;//搜索过程中的KFC的个数,初始为0 queue
q; node aa,bb; aa.x=x; aa.y=y; if(!flag)//flag=0的时候执行Y的bfs a[x][y]=0; else b[x][y]=0;//flag=1的时候执行M的bfs q.push(aa); while(!q.empty()) { bb=q.front(); q.pop(); if(k==kcount) break;//退出条件 ,当搜索过程中访问过的KFC数量等于整个地图总的KFC数量时就可以退出,剩下的节点不需要再访问 for(int i=0;i<4;i++) { aa.x=bb.x+dx[i]; aa.y=bb.y+dy[i]; if(!flag)//Y的bfs { if(aa.x>=0&&aa.x
=0&&aa.y
=0&&aa.x
=0&&aa.y
>n>>m) { memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); kcount=0; flag=0; getmap(); bfs(yx,yy); flag=1; bfs(mx,my); int minn=1000000; for(int i=0;i

运行截图:

2014.3.3  修改

最近又重新做这个题,发现上面写的代码虽然能通过,但是错误的!  

if(aa.x>=0&&aa.x
=0&&aa.y

map[aa.x][bb.y]这里应该是map[aa.x][aa.y]才对,当时不知道为什么会写成那样,而且能通过,更不得其解,但是后来改回来以后,提交竟然通不过了!为这个问题困扰了两天!下午,让老师帮我看看。后来老师出了一个神测试数据。

4 5

@  .  # @ .
  .   .  Y #  .
@ # M #  .
@  .  .  # @      这个测试数据用我改后的代码竟然输出为0,后来用别人的其他能在航电上通过的代码测试,输出也是0,但该测试数据结果应该为77才对。这就说明了该题后台测试数据不全面。

后来想了想为什么会输出为0,该测试数据很特殊,因为第四列@和第五列的@在广搜时搜不到!因为被墙#完全隔着,其步数永远是0,后来在遍历全图,取两人在@处最小步数时,肯定是没有搜到的@处最小,因为二者到此处的步数均为0,想加也为0,所以必须得加一个限制条件,取@处二者步数相加和的最小且该@处必须已经被搜过!加上这一句,代码就没问题了。我把上面提到的错误(map[aa.x][bb.y]这里应该是map[aa.x][aa.y]才对)改了以后,又在后面加上了限制条件,再重新提交,Ac了!哎,不容易啊,一桩心事终于了了!

下面附上修改后并优化后的代码:

#include 
#include
#include
#include
using namespace std;char map[202][202];//地图int a[202][202];//保存第一个人Y到各个节点(坐标)的最小步数,有的节点不用访问,下面有说明int b[202][202];//保存第二个人Mint dx[4]={0,0,-1,1};int dy[4]={1,-1,0,0};//方向int n,m;//地图大小int yx,yy,mx,my;//Y的坐标,M的坐标void getmap()//输入地图{ for(int i=0;i
>map[i][j]; if(map[i][j]=='Y') { yx=i; yy=j; } else if(map[i][j]=='M') { mx=i; my=j; } }}struct node{ int x,y;};void bfs(int x,int y,int num[202][202])//广搜{ queue
q; node aa,bb; aa.x=x; aa.y=y; num[x][y]=0; q.push(aa); while(!q.empty()) { bb=q.front(); q.pop(); for(int i=0;i<4;i++) { aa.x=bb.x+dx[i]; aa.y=bb.y+dy[i]; if(aa.x>=0&&aa.x
=0&&aa.y
>n>>m) { memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); getmap(); bfs(yx,yy,a); bfs(mx,my,b); int minn=1000000; for(int i=0;i

转载于:https://www.cnblogs.com/sr1993/p/3697809.html

你可能感兴趣的文章
移动端网页布局中需要注意事项以及解决方法总结
查看>>
(原创)Linux下查看系统版本号信息的方法
查看>>
oracle
查看>>
redis使用过程中主机内核层面的一些优化
查看>>
我也要谈谈大型网站架构之系列(2)——纵观历史演变(下)
查看>>
大话设计模式(Golang) 二、策略模式
查看>>
使用PostgreSQL 9.6 架设mediawiki服务器
查看>>
数据库服务器硬件对性能的影响
查看>>
LVM
查看>>
windows+群辉服务器环境下,搭建git版本管理
查看>>
Boolean类型
查看>>
Ubuntu 修改源
查看>>
php 几个比较实用的函数
查看>>
(译)OpenGL ES2.0 – Iphone开发指引
查看>>
@RestController 与 @RequestMapping
查看>>
黑马程序员.bobo.DAY.1
查看>>
Unity shader 官网文档全方位学习(二)
查看>>
pbrun
查看>>
浏览器加载和渲染网页顺序
查看>>
微服务架构springcloud
查看>>