#include<algorithm>
#include<queue>
#include<stdio.h>
#include<string.h>
using namespace std; const int maxn = ;
const int oo = 0xfffffff; struct node{int x, y, op;};//op等于0的时候代表是Y，1代表M
char G[maxn][maxn];
int v[maxn][maxn][];
int M, N;
int dir[][] = { {,},{,},{,-},{-,} }; int Bfs(node s, node q)
{
queue<node> Q;
int Min = oo;
Q.push(s), Q.push(q);
v[s.x][s.y][s.op] = v[q.x][q.y][q.op] = ; while(Q.size())
{
s = Q.front();Q.pop(); if(G[s.x][s.y] == '@' && v[s.x][s.y][] && v[s.x][s.y][])
Min = min(Min, v[s.x][s.y][]+v[s.x][s.y][]); for(int i=; i<; i++)
{
q = s;
q.x += dir[i][], q.y += dir[i][]; if(q.x>=&&q.x<M && q.y>=&&q.y<N && G[q.x][q.y] != '#' && v[q.x][q.y][q.op]==)
{
v[q.x][q.y][q.op] = v[s.x][s.y][s.op] + ;
Q.push(q);
}
}
} return Min-;
} int main()
{
while(scanf("%d%d", &M, &N) != EOF)
{
node s, q;
int i, j; for(i=; i<M; i++)
{
scanf("%s", G[i]);
for(j=; j<N; j++)
{
if(G[i][j] == 'Y')
s.x = i, s.y = j, s.op=;
if(G[i][j] == 'M')
q.x = i, q.y = j, q.op=;
}
} memset(v, , sizeof(v)); int ans = Bfs(s, q); printf("%d\n", ans*);
} return ;
}
随机推荐
-
Tsung安装与使用
Tsung安装与使用 Tsung安装与使用的详细说明,包括测试场景的脚本配置说明 Ray 2013/11/11 目录 安装tsung Tsung运行环境安装... Tsung安装... 使用Tsu ...
-
RMAN笔记小结
首先感谢junsansi和leshani两位大师的文笔:我可是好好看了很多遍:这两位哦:我跟你们说:对rman的解说那是相当精彩:文章形如流水,通俗易懂:内容那是入木三分...;好了我也不多说了,反正 ...
-
QT的三种协议说明
关于Qt的三种协议以及是否收费,有以下引文: 引文一: 最近一直在学习 Qt.Qt 有两个许可证:LGPL 和商业协议.这两个协议在现在的 Qt 版本中的代码是完全一致的(潜在含义是,Qt 的早期版本 ...
-
2017-07-06（grep man apropos ）
grep 格式 grep [选项] 字符串 文件名 选项 -i 忽略大小写 -v 排除指定字符串 作用 在文件中查找字符串 例子 grep "size" anaconda- ...
-
学习ASP.NET Core Razor 编程系列九——增加查询功能
学习ASP.NET Core Razor 编程系列目录 学习ASP.NET Core Razor 编程系列一 学习ASP.NET Core Razor 编程系列二——添加一个实体 学习ASP.NET ...
-
解决 Mac launchpad 启动台 Gitter 图标无法删除的问题
Mac 删除应用非常简单,将应用拖到回收站就删除了.或者进入应用程序文件夹,选中程序,command + delete 就删除了应用,这也是删除文件的快捷键. 但是,安装 Gitter 后,删除了应用 ...
-
rsyslog和logrotate服务
参考: http://www.lampbo.org/others/opensource/rsyslog-config-file-detail.html http://bangerlee.blog.ch ...
-
51Nod1376 (dp + BIT // cdq分治)
https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1376 求LIS的数量. 乍一看觉得还是dp,仔细一看确实可以用dp做. ...
-
Activity四大启动模式
ctivity的四种启动模式: standard.singleTop.singleTask.singleInstance 为了打印方便,定义一个基础Activity,在其onCreate方法和onNe ...
-
ID、Class和标签选择器优先级
按一般论:ID > Class > 标签 1.如以下样式: <div id="id" class="class">选择器优先权</ ...