#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 ;
}
随机推荐
-
iOS: 在代码中使用Autolayout (2) – intrinsicContentSize和Content Hugging Priority【转】
原文:http://www.mgenware.com/blog/?p=491 接上文:iOS: 在代码中使用Autolayout (1) – 按比例缩放和优先级. 我们继续来看在代码中使用Autola ...
-
解决每次升级Xcode后三方插件失效问题
其实就是插件里面的UIID没有加新XcodedeUIID 拿常用的Alactraz来说 在Terminal中 un these 2 lines in terminal:1:find ~/Library ...
-
Missing iOS Distribution signing identity问题解决
问题描述 打包上传APPStore Xcode报以下错误:Missing iOS Distribution signing identity for XXXXXX 查看证书后发现,Develop证书 ...
-
SGU 165.Basketball
题意 输入n个在[1.95,2.05]范围内的数. 保证他们的平均数为2.00. 现在要求把这些数调整出一个顺序, 使得任意长度为K的子段和与2.00* ...
-
使用BeanUtils组件
使用BeanUtils组件 前提 1:导入commons-beanutils-1.8.3.jar //根据 本人使用的是1.8.3的版本 2:导入日志包 //就是loggin ...
-
搜索所有的路径-矩阵运算-暴力-ACM
给定一个n*n整数矩阵,定义对I行的SHIFT操作( 0 <= i < n ),是将第I行所有元素都右移一位,最右边的移到最左边. 你可以对任意行进行任意次SHIFT操作,使得: max0 ...
-
QTP插入Output Value和插入CheckPoint，注意点
1. 必须打开程序才能进行Output value和CheckPoint的插入. 2. 也有可能是对象获取不到,从新加载对象库. 提示如下图:
-
php报警：Strict Standards: Only variables should be passed by reference in
错误原因 因为end函数的原因. end函数: mixed end ( array &$array ) 你可以看到end的参数是一个引用(reference),而你只能把一个变量的引 ...
-
YII 验证功能
YII 表单的验证可以在module目录下的xxx.php里面定义验证方法,设定需要验证的字段就行 //用户表单验证,在模型里面设置一个方法,具体表单验证规则 public functi ...
-
C语言学习笔记（二）：指针的用法
与其说指针是一种工具,不如先说指针是一种数据类型. -------------------------------------------------------------华丽的分割线------- ...