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.
InputThe 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
OutputFor 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 主要思想：不能直接用枚举，这样容易超时（不信可以试试）。用bfs把每一个位置遍历，发现@就记录一下。其中也有一些问题，比如怎么对每一个@进行区别，和如果有一个@两个人都不能到达或者有一个人不能到达怎么办（这个需要读题仔细）。
解决方法：用二维数组，对@位置进行记录，再用一个一维数组判断是不是两个人都到了。
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<queue>
#define INF 10000
using namespace std;
typedef pair<int,int> ee;
bool vis[209][209];
int t[4][2]={0,1,1,0,-1,0,0,-1};
int d[209][209];
char a[209][209];
int b[1009][1009];
int g[1009][1009];
queue<ee> que;
int n,m,k;
int tx,ty,sx,sy,mx,my;
{
while(!que.empty()) que.pop();
return;
}
{
memset(d,0,sizeof(d));
memset(vis,0,sizeof(vis));
d[x][y]=0;
que.push(ee(x,y));
vis[x][y]=true;
{
ee exa=que.front();
que.pop();
if(a[exa.first][exa.second]=='@')
{
b[exa.first][exa.second]=b[exa.first][exa.second]+d[exa.first][exa.second];
g[exa.first][exa.second]++;
}
for(int i=0;i<4;i++)
{
tx=exa.first+t[i][0];
ty=exa.second+t[i][1];
if(a[tx][ty]=='#') continue;
if(vis[tx][ty]) continue;
vis[tx][ty]=true;
d[tx][ty]=d[exa.first][exa.second]+1;
// printf("%d\n",d[tx][ty]);
}
}
clean();
return;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
k=0;
memset(b,INF,sizeof(b));
memset(g,0,sizeof(g));
for(int i=1;i<=n;i++)
{
scanf("%s",a[i]+1);
for(int j=1;j<=m;j++)
{
if(a[i][j]=='Y'){sx=i;sy=j;}
if(a[i][j]=='M'){mx=i;my=j;}
if(a[i][j]=='@'){b[i][j]=0;}
}
}
bfs(sx,sy);
bfs(mx,my);
int x1=1,x2=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(b[i][j]<b[x1][x2]&&g[i][j]==2)
{
b[x1][x2]=b[i][j];
}
}
}
printf("%d\n",b[x1][x2]*11);
}
}
随机推荐
-
移动端的拖拽这个demo实现的功能
SQL数据库适合那些需求确定和对数据完整性要去严格的项目.NoSQL数据库适用于那些对速度和可扩展性比较看重的那些不相关的,不确定和不断发展的需求. 总所周知,网页的加载速度跟图片是有很大的关系的,因 ...
-
css部分的复习
常见的块元素有<h1><h6>.<p><div><ul><li><ol>等,其中<div>标记是最典型的 ...
-
Python 基础语法(二)
Python 基础语法(二) --------------------------------------------接 Python 基础语法(一) ------------------------ ...
-
ASP.NET MVC 从IHttp到页面输出
MVCHandler应该算是MVC真正开始的地方.MVCHandler实现了IHttpHandler接口,ProcessRequest便是方法入口. MVCHandler : IHttpHandler ...
-
[MAXscript Tool]FFX_PalyBack v1.1 ShowReel
自己的写的一个简单的脚本方便实现大面积的烟,火,爆炸,云的效果.能实现静态动态的切换,还有快速的偏移FumeFX的缓存,支持随机缓存 具体看这个插件的ShowReel,结算的三套基础的火焰然后用此脚本 ...
-
PAT1008
1008. Elevator (20) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B The highest building in our city has on ...
-
java 注解 知识整理
一.前言 注解(也称为元数据)为我们在代码中添加信息提供了一种方法,它在 一定程度上将元数据与源代码文件结合在一起.它是从java 5 开始引入的.通过使用注解,我们可以将元数据保存在Java源代码之 ...
-
如何在Mac 终端上Git 项目的一次常规操作
首先,Git的工作流是怎样的? 你的本地仓库由 git 维护的三棵“树”组成. 第一个是你的 工作目录,它持有实际文件: 第二个是 暂存区(Index),它像个缓存区域,临时保存你的改动: 最后是 H ...
-
工业以太网EtherNet/IP协议安全分析整理
1. EtherNet/IP : 设备可以用户数据报协议(UDP)的隐式报文传送基于IO的资料 ,用户传输控制协议(TCP)显示报文上传和下参数,设定值,程式 ,用户主站的轮询 从站周期性的更 ...
-
51Nod 1677 treecnt
一道比较基础的计数题,还是一个常用的单独计算贡献的例子. 首先看题目和范围,暴力枚举肯定是不可行的,而且\(O(n\ logn)\)的算法貌似很难写. 那我们就来想\(O(n)\)的吧,我们单独考虑每 ...