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

95 阅读 0 评论 63 点赞

我是靠谱客的博主勤劳钢笔，最近开发中收集的这篇文章主要介绍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("%dn", bfs(n, m));
73 
}
74
system("pause");
75
return 0;
76 }