HDU.2612 Find a way （BFS）
题意分析
圣诞节要到了，坤神和瑞瑞这对基佬想一起去召唤师大峡谷开开车。百度地图一下，发现周围的召唤师大峡谷还不少，这对基佬纠结着，该去哪一个。。。坤神：我要去左边的这个（因为离自己比较近 哈哈~）。。瑞瑞：我要去右边的这个（因为离自己比较近 嘿嘿~） ……..这对基佬闹矛盾了，开车有危险了！ 为了不让他们去召唤师大峡谷坑人，riot决定让他们去X召唤师大峡谷，保证他俩所走的路程和最短。每走一个点需要花费11分钟，输出他们一共花费多少时间（最短时间噢）
多组测试数据
每组数据，开始一行n，m (2<=n,m<=200)
接下来是个n x m的矩阵
‘Y’ 表示坤神所在的初始位置
‘M’ 表示瑞瑞所在的初始位置
‘#’ 该点禁止通行
‘.’ 该点可通行
‘@’ 召唤师大峡谷
直接BFS，即可，可以认为YM互相走，即Y可以通过M，M可以通过Y。开两个二维数组，来表示Y和M分别到达一个@时，所需要的时间。当然需要注意有些@是无法到达的，所以最后检查最小时间的时候，若有一方的时间为0，需要跳过。
代码总览
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#define nmax 205
using namespace std;
char mp[nmax][nmax];
int Ytime[nmax][nmax],Mtime[nmax][nmax];
bool visit[nmax][nmax];
typedef struct{
int x;
int y;
int times;
}mes;
int n,m;
int spx[4] = {0,1,0,-1};
int spy[4] = {1,0,-1,0};
mes Y,M;
bool check(mes temp)
{
if(temp.x <0 || temp.x >=n || temp.y <0 || temp.y >= m || visit[temp.x][temp.y] || mp[temp.x][temp.y] == '#')
return false;
else return true;
}
void bfsY()
{
memset(visit,0,sizeof(visit));
queue<mes> q;
mes temp = Y ,head;
visit[temp.x][temp.y] = true;
q.push(temp);
while(!q.empty()){
head = q.front();q.pop();
if(mp[head.x][head.y] == '@'){
Ytime[head.x][head.y] = head.times;
}
for(int i = 0;i<4;++i){
temp.x = head.x + spx[i];
temp.y = head.y + spy[i];
temp.times = head.times + 1;
if(check(temp)){
visit[temp.x][temp.y] = true;
q.push(temp);
}
}
}
}
void bfsM()
{
memset(visit,0,sizeof(visit));
queue<mes> q;
mes temp = M ,head;
visit[temp.x][temp.y] = true;
q.push(temp);
while(!q.empty()){
head = q.front();q.pop();
if(mp[head.x][head.y] == '@'){
Mtime[head.x][head.y] = head.times;
}
for(int i = 0;i<4;++i){
temp.x = head.x + spx[i];
temp.y = head.y + spy[i];
temp.times = head.times + 1;
if(check(temp)){
visit[temp.x][temp.y] = true;
q.push(temp);
}
}
}
}
int main()
{
while(scanf("%d %d",&n,&m) != EOF){
vector<mes> v; v.clear();
for(int i = 0;i<n;++i){
for(int j = 0;j<m;++j){
scanf(" %c",&mp[i][j]);
if(mp[i][j] == 'Y'){
Y.x = i;
Y.y = j;
Y.times = 0;
}else if(mp[i][j] == 'M'){
M.x = i;
M.y = j;
M.times = 0;
}else if(mp[i][j] == '@'){
v.push_back((mes){i,j,0});
}
}
}
bfsY();
bfsM();
int ans = 100000;
for(int i = 0;i<v.size();++i){
if(Ytime[v[i].x][v[i].y] == 0 || Mtime[v[i].x][v[i].y] == 0) continue;
else if(ans > Ytime[v[i].x][v[i].y] + Mtime[v[i].x][v[i].y]){
ans = Ytime[v[i].x][v[i].y] + Mtime[v[i].x][v[i].y];
}
}
printf("%d\n",ans * 11);
}
return 0;
}