hdoj 2612 find a way (两次bfs)
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 }
148
149
150