Find a way#
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 6221 Accepted Submission(s): 2070
Problem Description
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.
Input
The 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
Output
For 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
Author
yifenfei
Source
一开始写成了对每个肯德基店做一次 bfs，会 TLE
之后发现，对两个人分别做一次 bfs 就行
只是遇到肯德基店的时候，因为不能确定这个是否是最优的，所以不 return，继续搜下去。
代码实现
1
2
3
4 /*************************************************************************
5 > File Name: code/2015summer/searching/N.cpp
6 > Author: 111qqz
7 > Email: rkz2013@126.com
8 > Created Time: 2015年07月25日 星期六 13时54分49秒
9 ************************************************************************/
10
11 #include<iostream>
12 #include<iomanip>
13 #include<cstdio>
14 #include<algorithm>
15 #include<cmath>
16 #include<cstring>
17 #include<string>
18 #include<map>
19 #include<set>
20 #include<queue>
21 #include<vector>
22 #include<stack>
23 #define y0 abc111qqz
24 #define y1 hust111qqz
25 #define yn hez111qqz
26 #define j1 cute111qqz
27 #define tm crazy111qqz
28 #define lr dying111qqz
29 using namespace std;
30 #define REP(i, n) for (int i=0;i<int(n);++i)
31 typedef long long LL;
32 typedef unsigned long long ULL;
33 const int N= 2E2+5;
34 char st[N][N];
35 int n,m;
36 int d[N][N];
37 int dd[N][N];
38 int dx[4]={0,0,-1,1};
39 int dy[4]={1,-1,0,0};
40 struct node
41 {
42 int x,y;
43 }kfc[N];
44 node M,Y;
45 void bfs(int xo,int yo)
46 {
47 memset(d,-1,sizeof(d));
48 queue<int>x;
49 queue<int>y;
50 x.push(xo);
51 y.push(yo);
52 d[xo][yo]=0;
53 while (!x.empty())
54 {
55 int px=x.front();x.pop();
56 int py=y.front();y.pop();
57 for ( int i = 0 ; i < 4 ; i++ )
58 {
59 int nx = px+dx[i];
60 int ny = py+dy[i];
61 if (nx>=0&&nx<n&&ny>=0&&ny<m&&d[nx][ny]==-1&&st[nx][ny]!='#')
62 {
63 d[nx][ny]=d[px][py]+1;
64 x.push(nx);
65 y.push(ny);
66 }
67 }
68
69 }
70 // cout<<"res1:"<<res<<endl;
71 }
72 void bfs2(int xo,int yo)
73 {
74 memset(dd,-1,sizeof(dd));
75 queue<int>x;
76 queue<int>y;
77 x.push(xo);
78 y.push(yo);
79 dd[xo][yo]=0;
80 while (!x.empty())
81 {
82 int px = x.front();x.pop();
83 int py =y.front();y.pop();
84 for ( int i = 0 ; i <4 ; i++ )
85 {
86 int nx = px +dx[i];
87 int ny = py +dy[i];
88 if (nx>=0&&nx<n&&ny>=0&&ny<m&&dd[nx][ny]==-1&&st[nx][ny]!='#')
89 {
90 dd[nx][ny]= dd[px][py]+1;
91 x.push(nx);
92 y.push(ny);
93 }
94 }
95 }
96
97 }
98
99
100
101
102 int main()
103 {
104 while (scanf("%d %d",&n,&m)!=EOF)
105 {
106 for ( int i = 0 ; i < n ; i++ )
107 {
108 cin>>st[i];
109 }
110 int k = 0;
111 for ( int i = 0 ; i < n ; i++)
112 {
113 for ( int j = 0 ; j < m ; j++ )
114 {
115 if (st[i][j]=='Y')
116 {
117 Y.x=i;
118 Y.y=j;
119 }
120 if (st[i][j]=='M')
121 {
122 M.x=i;
123 M.y=j;
124 }
125 }
126 }
127 bfs(Y.x,Y.y);
128 bfs2(M.x,M.y);
129 int ans = 99999999;
130 for ( int i = 0 ; i < n ; i++ )
131 {
132 for ( int j = 0 ; j < m ; j++ )
133 {
134 if (st[i][j]=='@')
135 {
136 // cout<<d[i][j]<<" "<<dd[i][j]<<endl;
137 if (d[i][j]==-1||dd[i][j]==-1) continue;
138 ans = min(ans,d[i][j]+dd[i][j]);
139 }
140 }
141 }
142
143 cout<<ans*11<<endl;
144 }
145
146 return 0;
147 }