Find a way HDU

Find a way

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.

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

题意：

圣诞节要到了，坤神和瑞瑞这对基佬想一起去召唤师大峡谷开开车。百度地图一下，发现周围的召唤师大峡谷还不少，这对基佬纠结着，该去哪一个。。。坤神：我要去左边的这个（因为离自己比较近 哈哈~）。。瑞瑞：我要去右边的这个（因为离自己比较近 嘿嘿~） ........这对基佬闹矛盾了，开车有危险了！  为了不让他们去召唤师大峡谷坑人，riot决定让他们去X召唤师大峡谷，保证他俩所走的路程和最短。每走一个点需要花费11分钟，输出他们一共花费多少时间（最短时间噢）
Input
多组测试数据

每组数据，开始一行n，m (2<=n,m<=200)

接下来是个n x m的矩阵

'Y' 表示坤神所在的初始位置

'M' 表示瑞瑞所在的初始位置

'#' 该点禁止通行

'.' 该点可通行

'@' 召唤师大峡谷

Output
每组测试数据，输出坤神和瑞瑞到达同一个召唤师大峡谷所花费的最短时间。

思路：

bfs分别求出两个人到各个点的最短时间存在dis数组中，遍历map寻找和最小的那个点。

代码：

  1 #include <set>
  2 //#include <map>
  3 #include <list>
  4 #include <stack>
  5 #include <queue>
  6 #include <deque>
  7 #include <cmath>
  8 #include <string>
  9 #include <vector>
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <cstdlib>
 13 #include <sstream>
 14 #include <iostream>
 15 #include <algorithm>
 16 //#include <unordered_map>
 17 #define INF 0x3f3f3f3f
 18 #define ll long long
 19 #define ull unsigned long long
 20 #define FILL(a,n,v) fill(a,a+n,v)
 21 #define Mset(a,v) memset(a,v,sizeof a)
 22 #define fcio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
 23 using namespace std;
 24 const int maxn=300;
 25 
 26 int dis1[maxn][maxn],dis2[maxn][maxn];
 27 int n,m;
 28 string map[maxn];
 29 int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
 30 struct node
 31 {
 32     int x,y;
 33     int step;
 34     node(int x,int y)
 35     {
 36         this->x=x;
 37         this->y=y;
 38         this->step=0;
 39     }
 40 };
 41 
 42 bool vis[maxn][maxn];
 43 bool check(int x,int y)
 44 {
 45     if(!((x>=0)&&(x<n)&&(y>=0)&&(y<m))) return false;
 46     if(map[x][y]=='#') return false;
 47     if(!vis[x][y]) return false;
 48     return true;
 49 }
 50 
 51 void bfs1(int x,int y)
 52 {
 53     memset(vis,true,sizeof vis);
 54     vis[x][y]=false;
 55     node now(x,y);
 56     queue<node>q;
 57     q.push(now);
 58     while(!q.empty())
 59     {
 60         now=q.front();
 61         q.pop();
 62         if(map[now.x][now.y]=='@')
 63         {
 64             dis1[now.x][now.y]=now.step;
 65         }
 66         for(int i=0;i<4;i++)
 67         {
 68             int nx=now.x+dir[i][0];
 69             int ny=now.y+dir[i][1];
 70             if(check(nx,ny))
 71             {
 72                 vis[nx][ny]=false;
 73                 node next(nx,ny);
 74                 next.step=now.step+11;
 75                 q.push(next);
 76             }
 77         }
 78     }
 79 }
 80 
 81 void bfs2(int x,int y)
 82 {
 83     memset(vis,true,sizeof vis);
 84     vis[x][y]=false;
 85     node now(x,y);
 86     queue<node>q;
 87     q.push(now);
 88     while(!q.empty())
 89     {
 90         now=q.front();
 91         q.pop();
 92         if(map[now.x][now.y]=='@')
 93         {
 94             dis2[now.x][now.y]=now.step;
 95         }
 96         for(int i=0;i<4;i++)
 97         {
 98             int nx=now.x+dir[i][0];
 99             int ny=now.y+dir[i][1];
100             if(check(nx,ny))
101             {
102                 vis[nx][ny]=false;
103                 node next(nx,ny);
104                 next.step=now.step+11;
105                 q.push(next);
106             }
107         }
108     }
109 }
110 
111 int main()
112 {
113     while(cin>>n>>m)
114     {
115         int x1=0,y1=0,x2=0,y2=0;
116         for(int i=0;i<n;i++) cin>>map[i];
117         for(int i=0;i<n;i++)
118         {
119             for(int j=0;j<m;j++)
120             {
121                 if(map[i][j]=='Y')
122                 {
123                     x1=i;
124                     y1=j;
125                 }
126                 if(map[i][j]=='M')
127                 {
128                     x2=i;
129                     y2=j;
130                 }
131             }
132         }
133         Mset(dis1,INF);
134         Mset(dis2,INF);
135         bfs1(x1,y1);
136         bfs2(x2,y2);
137         int res=INF;
138         for(int i=0;i<n;i++)
139         {
140             for(int j=0;j<m;j++)
141             {
142                 res=min(res,dis1[i][j]+dis2[i][j]);
143             }
144         }
145         cout<<res<<endl;
146     }
147 }