1 /*
2 BFS：和UVA_11624差不多，本题就是分别求两个点到KFC的最短路，然后相加求最小值
3 */
4 /************************************************
5 Author :Running_Time
6 Created Time :2015-8-4 19:36:36
7 File Name :HDOJ_2612.cpp
8 ************************************************/
9
10 #include <cstdio>
11 #include <algorithm>
12 #include <iostream>
13 #include <sstream>
14 #include <cstring>
15 #include <cmath>
16 #include <string>
17 #include <vector>
18 #include <queue>
19 #include <deque>
20 #include <stack>
21 #include <list>
22 #include <map>
23 #include <set>
24 #include <bitset>
25 #include <cstdlib>
26 #include <ctime>
27 using namespace std;
28
29 #define lson l, mid, rt << 1
30 #define rson mid + 1, r, rt << 1 | 1
31 typedef long long ll;
32 const int MAXN = 2e2 + 10;
33 const int INF = 0x3f3f3f3f;
34 const int MOD = 1e9 + 7;
35 char maze[MAXN][MAXN];
36 bool vis[MAXN][MAXN];
37 int step[MAXN][MAXN];
38 int step2[MAXN][MAXN];
39 int dx[4] = {-1, 1, 0, 0};
40 int dy[4] = {0, 0, -1, 1};
41 int n, m;
42 int sx, sy, ex, ey;
43
44 bool judge_y(int x, int y) {
45 if (x < 1 || x > n || y < 1 || y > m || maze[x][y] == '#' || vis[x][y]) return false;
46 return true;
47 }
48
49 bool judge_m(int x, int y) {
50 if (x < 1 || x > n || y < 1 || y > m || maze[x][y] == '#' || vis[x][y]) return false;
51 return true;
52 }
53
54 void BFS_Y(void) {
55 memset (step, 0, sizeof (step));
56 memset (vis, false, sizeof (vis));
57 queue<pair<int, int> > Q; Q.push (make_pair (sx, sy));
58 vis[sx][sy] = true; step[sx][sy] = 0;
59 while (!Q.empty ()) {
60 int x = Q.front ().first, y = Q.front ().second; Q.pop ();
61 for (int i=0; i<4; ++i) {
62 int tx = x + dx[i], ty = y + dy[i];
63 if (!judge_y (tx, ty)) continue;
64 Q.push (make_pair (tx, ty)); vis[tx][ty] = true;
65 step[tx][ty] = step[x][y] + 1;
66 }
67 }
68 }
69
70 void BFS_M(void) {
71 memset (vis, false, sizeof (vis));
72 memset (step2, 0, sizeof (step2));
73 queue<pair<int, int> > Q; Q.push (make_pair (ex, ey));
74 vis[ex][ey] = true; step2[ex][ey] = 0;
75 while (!Q.empty ()) {
76 int x = Q.front ().first, y = Q.front ().second; Q.pop ();
77 for (int i=0; i<4; ++i) {
78 int tx = x + dx[i], ty = y + dy[i];
79 if (!judge_m (tx, ty)) continue;
80 step2[tx][ty] = step2[x][y] + 1;
81 Q.push (make_pair (tx, ty)); vis[tx][ty] = true;
82 }
83 }
84 }
85
86 int main(void) { //HDU 2612 Find a way
87 while (scanf ("%d%d", &n, &m) == 2) {
88 for (int i=1; i<=n; ++i) {
89 scanf ("%s", maze[i] + 1);
90 for (int j=1; j<=m; ++j) {
91 if (maze[i][j] == 'Y') sx = i, sy = j;
92 if (maze[i][j] == 'M') ex = i, ey = j;
93 }
94 }
95 BFS_Y (); BFS_M ();
96 int ans = INF;
97 for (int i=1; i<=n; ++i) {
98 for (int j=1; j<=m; ++j) {
99 if (maze[i][j] == '@' && vis[i][j]) {
100 ans = min (ans, step[i][j] + step2[i][j]);
101 }
102 }
103 }
104 if (ans == INF) puts ("-1");
105 else printf ("%d
", ans * 11);
106 }
107
108 return 0;
109 }
BFS(最短路) HDU 2612 Find a way
编译人生，运行世界！