Posted on 2009-04-23 12:58
superman 阅读(175)
评论(0) 编辑 收藏 引用 所属分类:
USACO
1 #include <queue>
2 #include <iostream>
3
4 using namespace std;
5
6 struct Point
7 {
8 int x, y;
9 } ;
10
11 int n, m, ans;
12 int rec[100 * 2 + 1][38 * 2 + 1];
13 char map[100 * 2 + 1][38 * 2 + 1];
14
15 bool inside(int i, int j)
16 {
17 return i >= 1 && i < n - 1 && j >= 1 && j < m - 1;
18 }
19
20 void bfs(Point & cp)
21 {
22 rec[cp.x][cp.y] = 1;
23
24 queue <Point> q;
25 q.push(cp);
26
27 while (q.empty() == false)
28 {
29 Point cp = q.front(); q.pop();
30
31 if (inside(cp.x - 1, cp.y) && map[cp.x - 1][cp.y] == ' ')
32 if (rec[cp.x][cp.y] + 1 < rec[cp.x - 1][cp.y])
33 {
34 rec[cp.x - 1][cp.y] = rec[cp.x][cp.y] + 1;
35 Point np = { cp.x - 1, cp.y };
36 q.push(np);
37 }
38 if (inside(cp.x + 1, cp.y) && map[cp.x + 1][cp.y] == ' ')
39 if (rec[cp.x][cp.y] + 1 < rec[cp.x + 1][cp.y])
40 {
41 rec[cp.x + 1][cp.y] = rec[cp.x][cp.y] + 1;
42 Point np = { cp.x + 1, cp.y };
43 q.push(np);
44 }
45 if (inside(cp.x, cp.y - 1) && map[cp.x][cp.y - 1] == ' ')
46 if (rec[cp.x][cp.y] + 1 < rec[cp.x][cp.y - 1])
47 {
48 rec[cp.x][cp.y - 1] = rec[cp.x][cp.y] + 1;
49 Point np = { cp.x, cp.y - 1 };
50 q.push(np);
51 }
52 if (inside(cp.x, cp.y + 1) && map[cp.x][cp.y + 1] == ' ')
53 if (rec[cp.x][cp.y] + 1 < rec[cp.x][cp.y + 1])
54 {
55 rec[cp.x][cp.y + 1] = rec[cp.x][cp.y] + 1;
56 Point np = { cp.x, cp.y + 1 };
57 q.push(np);
58 }
59 }
60 }
61
62 int main()
63 {
64 freopen("maze1.in", "r", stdin);
65 freopen("maze1.out", "w", stdout);
66
67 cin >> m >> n;
68
69 n = 2 * n + 1;
70 m = 2 * m + 1;
71
72 cin.get();
73 for (int i = 0; i < n; i++)
74 {
75 for (int j = 0; j < m; j++)
76 map[i][j] = cin.get();
77 cin.get();
78 }
79
80 for (int i = 0; i < n; i++)
81 for (int j = 0; j < m; j++)
82 rec[i][j] = INT_MAX;
83
84 for (int i = 0, j = 0; j < m; j++)
85 if (map[i][j] == ' ')
86 {
87 Point p = { i, j };
88 bfs(p);
89 }
90 for (int i = 0, j = 0; i < n; i++)
91 if (map[i][j] == ' ')
92 {
93 Point p = { i, j };
94 bfs(p);
95 }
96 for (int i = n - 1, j = 0; j < m; j++)
97 if (map[i][j] == ' ')
98 {
99 Point p = { i, j };
100 bfs(p);
101 }
102 for (int i = 0, j = m - 1; i < n; i++)
103 if (map[i][j] == ' ')
104 {
105 Point p = { i, j };
106 bfs(p);
107 }
108
109 for (int i = 0; i < n; i++)
110 for (int j = 0; j < m; j++)
111 if (rec[i][j] != INT_MAX)
112 ans >?= rec[i][j];
113
114 cout << ans / 2 << endl;
115
116 return 0;
117 }
118