bjfu 1143 小蝌蚪安家(bfs入门）

本人的第一题bfs搜索：

在一个矩形区域内，有些地方有水，有些地方没水。所有相邻的有水的地方会共同组成一个水洼，小蝌蚪想在这块区域中找到一个最大的水洼来安家。

Input

有多组输入数据，每组第一行包含两个正整数n，m（n，m<=100），接下来n行，每行m个字符，“.”表示有水，“#”表示没水。

Output

对于每组输入数据输出一行，包含一个整数，表示最大的水洼的面积。

Sample Input

3 3
###
###
##.
2 3
#..
..#
3 3
##.
#..
.##

Sample Output

1
4
3

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <queue>
 4 int dir[][2] = {{-1,0}, {0,1}, {1,0}, {0,-1}};   //上下左右四个方向
 5 const int MAXN = 105;
 6 char map[MAXN][MAXN];
 7 bool vis[MAXN][MAXN];
 8 int n, m;
 9 struct Node
10 {
11     int x, y;
12 };
13 void init(char (*a)[MAXN])                    //用来初始化map
14 {
15     for (int i = 0; i < n; ++i)
16         for (int j = 0; j < m; ++j)
17         {
18             if (a[i][j] == '.')        
19                 vis[i][j] = 0;
20             else
21                 vis[i][j] = 1;
22         }
23 }
24 int bfs(int n, int m)
25 {
26     Node tmp, next;
27     int max = 0;
28     for (int i = 0; i < n; ++i)
29         for (int j = 0; j < m; ++j)
30             if (!vis[i][j])
31             {
32                 int cnt = 0;
33                 tmp.x = i;
34                 tmp.y = j;
35                 std::queue<Node> q;
36                 q.push(tmp);
37                 vis[tmp.x][tmp.y] = 1;
38                 while (!q.empty())
39                 {
40                     ++cnt;
41                     tmp = q.front();
42                     q.pop();
43                     for (int t = 0; t < 4; ++t)
44                     {
45                         next.x = tmp.x + dir[t][0];
46                         next.y = tmp.y + dir[t][1];
47                         if (next.x>=0 && next.x<n && next.y>=0 && next.y<m
48                                 && !vis[next.x][next.y])
49                         {
50                             vis[next.x][next.y] = 1;
51                             q.push(next);
52                         }
53                     }
54                 }
55                 if (cnt > max)
56                     max = cnt;
57             }
58     return max;
59 }
60 int main()
61 {
62     while (scanf("%d %d", &n, &m) != EOF)
63     {
64         getchar();                            //用cin输入char可以避免使用getchar();
65         for (int i = 0; i < n; ++i)
66         {
67             for (int j = 0; j < m; ++j)
68                 scanf("%c", &map[i][j]);
69             getchar();
70         }
71         init(map);
72         printf("%d\n", bfs(n, m));
73     }
74     system("pause");
75     return 0;
76 }