P8662 [蓝桥杯 2018 省 AB] 全球变暖 题解

· · 题解

1. 编程思路。

对给定海域中的每个陆地像素，从它出发用 BFS 搜索包括这个陆地像素的连通块，置连通块中的每个路地像素 (i,j) 的 vis_{i,j}=1，同时对连通块中的每个陆地像素的上下左右四个像素进行判断，若其上下左右这四个像素也是陆地像素 #，则其不会被淹没，对表示一个连通块中不会淹没的陆地进行计数，即 left 加 1。若一个连通块的 left 值为 0，表示这个连通块中的陆地像素都会被淹没，这个岛屿也就全被淹没了。

用 BFS 找出每个连通块，所有连通块中 left 值为 0 的连通块个数就是被淹没的岛屿数。

2. 源程序。

#include <stdio.h>
#include <string.h>
#define N 1005
char a[N][N];
int n,vis[N][N],dir[4][2]={{-1,0},{0,-1},{0,1},{1,0}};
struct Point
{
    int x,y;
};
struct Point q[1000000];
int bfs(int x,int y)
{
    struct Point p;
    p.x=x;  p.y=y;
    int front=0,rear=0;
    q[rear++]=p;
    int left=0;    // 表示一个连通块中留下的没有被淹没的陆地像素
    while (front<rear)
    {
        p=q[front++];
        int i,cnt=0;
        for (i=0;i<4;i++)
        {
            int dx=p.x+dir[i][0];
            int dy=p.y+dir[i][1];
            if (dx<0 || dx>=n || dy<0 || dy>=n)
                continue;
            if (a[dx][dy]=='#')   
            {
                cnt++;
                if (!vis[dx][dy])
                {
                    vis[dx][dy]=1;
                    q[rear].x=dx;
                    q[rear].y=dy;
                    rear++;
                }
            }
        }
        if (cnt==4)    // 如果一个陆地像素的上下左右四个方向也是陆地像素
            left++;    // 这个陆地像素肯定不会被淹没，留下了
    }
    return left;
}
int main()
{
    int i,j,ans=0;
    scanf("%d",&n);
    for (i=0;i<n;i++)
    {
        scanf("%s",a[i]);
    }
    memset(vis,0,sizeof(vis));
    for (i=0;i<n;i++)
    {
        for (j=0;j<n;j++)
        {
            if (a[i][j]=='#'&& !vis[i][j])  // 从这个没有访问过的陆地像素出发寻找其连通块
            {
                vis[i][j]=1;
                if (!bfs(i,j))    // 包含(i,j)陆地像素的连通块中的陆地像素全部被淹没，left=0
                    ans++;        // 被淹没的岛屿个数加 1
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}