Feeding Time 【bfs求最大连通块】

题目链接：https://ac.nowcoder.com/acm/contest/1870/J

题目大意：求最大的连通块是多大

主要是为了防止自己忘记bfs怎么写。。。。。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<queue>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAXN = 800;
 7 
 8 int l, h, vis[MAXN][MAXN];
 9 char map[MAXN][MAXN];
10 int dx[8] = {0, 0, 1, 1, 1, -1, -1, -1};  //方向数组 
11 int dy[8] = {1, -1, 1, 0, -1, 1, 0, -1};
12 
13 
14 struct Node
15 {
16     int x, y;
17 };
18 
19 int check(int x, int y)
20 {
21     if(x < 1 || x > h || y < 1 || y > l) //不越界 
22         return 0;
23     if(map[x][y] != '.') //不可走 
24         return 0;
25     if(vis[x][y] == 1) //已经走过 
26         return 0;
27     return 1;
28 }
29 
30 int bfs(int x, int y)
31 {
32     int sum = 0;
33     queue<Node> Q;
34     while(!Q.empty())    Q.pop();
35     Node no;
36     no.x = x, no.y = y;
37     vis[x][y] = 1;
38     sum ++;
39     Q.push(no);
40     while(!Q.empty())
41     {
42         Node a = Q.front();
43         Q.pop();
44         for(int k = 0; k < 8; k ++)
45         {
46             Node next = a;
47             next.x += dx[k];
48             next.y += dy[k];
49             if(check(next.x, next.y))
50             {
51                 sum ++;
52                 vis[next.x][next.y] = 1;
53                 Q.push(next);
54             }
55         }
56     }
57     return sum;
58 }
59 
60 int main()
61 {
62     int ans = -1;
63     scanf("%d%d", &l, &h);
64     getchar();
65     for(int i = 1; i <= h; i ++)
66         scanf("%s", map[i] + 1);
67     for(int i = 1; i <= h; i ++)
68         for(int j = 1; j <= l; j ++)
69             if(!vis[i][j] && map[i][j] == '.') //进入bfs的条件 
70                 ans = max(ans, bfs(i, j));
71     printf("%d
", ans);
72     return 0;
73 }

View Code