题目链接：http://poj.org/problem?id=1562 还是广搜比较好写啊……
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 #include <queue>
8 using namespace std;
9 int n, m, f[110][110];
10 char map[110][110];
11 struct nod{
12 int x, y;
13 };
14 queue<nod> Q;
15 const int dir[8][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {-1, 1}, {1, -1}, {-1, -1}};
16 bool inMap(int x, int y){
17 return x >= 0 && x < n && y >= 0 && y < m;
18 }
19 void bfs(int sx, int sy, int k){
20 f[sx][sy] = k;
21 nod S;
22 S.x = sx; S.y = sy;
23 Q.push(S);
24 while (!Q.empty()){
25 nod u = Q.front();
26 int x = u.x, y = u.y;
27 Q.pop();
28 for (int i = 0; i < 8; i++){
29 int xx = x + dir[i][0];
30 int yy = y + dir[i][1];
31 if (!inMap(xx, yy) || map[xx][yy] == '*') continue;
32 if (!f[xx][yy]){
33 f[xx][yy] = k;
34 nod v;
35 v.x = xx; v.y = yy;
36 Q.push(v);
37 }
38 }
39 }
40 }
41 int main(){
42 while (~scanf("%d%d", &n, &m)){
43 if (!m && !n) break;
44 for (int i = 0; i < n; i++) scanf("%s", map[i]);
45 memset(f, 0, sizeof(f));
46 int k = 1;
47 for (int i = 0; i < n; i++)
48 for (int j = 0; j < m; j++)
49 if (map[i][j] == '@' && !f[i][j]) bfs(i, j, k++);
50 int ans = 0;
51 for (int i = 0; i < n; i++)
52 for (int j = 0; j < m; j++)
53 ans = max(ans, f[i][j]);
54 printf("%d\n", ans);
55 }
56 return 0;
57
|