博客

标题：全球变暖

你有一张某海域NxN像素的照片，”.“表示海洋、”#”表示陆地，如下所示：

…

.##…

.##…

…##.

…####.

…###.

…

####其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。

####由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。

####例如上图中的海域未来会变成如下样子：

…

…

…

…

…#…

…

…

####请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

【输入格式】

第一行包含一个整数N。 (1 <= N <= 1000)

以下N行N列代表一张海域照片。

照片保证第1行、第1列、第N行、第N列的像素都是海洋。

【输出格式】

一个整数表示答案。

【输入样例】

7

…

.##…

.##…

…##.

…####.

…###.

…

【输出样例】

1

题目描述

.表示海洋，#表示陆地，如果一个陆地周围存在 . ，那么就会被海洋淹没，求被淹没的岛屿数量

思路：使用DFS对陆地进行搜索，并且对每个点进行判断，如果这个点被淹没，那么就记录为1，反之记录为2，如果一个点的周围已经有2或者3的时候，那么这个点就记录为3，这样做的目的是为了方便寻找没有被淹没的岛屿个数

代码如下

#include <iostream>
#include <math.h>
#include <stdio.h>
#include <queue>
#define N 1005
using namespace std;
char m[N][N];
int n,book[N][N],sum;
int next[4][2] = {
    {1,0},
    {0,1},
    {-1,0},
    {0,-1}
};
//判断当前搜索的点，并改变在book中的标记
void check(int x, int y)
{
    int i,tx,ty,flag = 0;
    //对这个点的上下左右都判断，如果这个点周围存在海洋，那么就标记为1
    for(i = 0;i < 4;i++)
    {
        tx = x + next[i][0];
        ty = y + next[i][1];
        if(tx < 0 || tx >= n || ty < 0 || ty >= n)
            continue;
        //如果这个点周围存在没有被淹没的陆地，那么就标记为3
        if(book[tx][ty] == 2 || book[tx][ty] == 3)
            flag = 1;
        if(m[tx][ty] == '.')
        {
            book[x][y] = 1;
            return;
        }
    }
    if(flag)
        book[x][y] = 3;
    else
        book[x][y] = 2;
}

void dfs(int x, int y)
{
    int i,tx,ty;
    check(x, y);
    for(i = 0;i < 4;i++)
    {
        tx = x + next[i][0];
        ty = y + next[i][1];
        if(tx < 0 || tx >= n || ty < 0 || ty >= n)
            continue;
        //搜索下一个没有搜索到的点
        if(!book[tx][ty] && m[tx][ty] == '#')
            dfs(tx,ty);
    }
    return;
}

int main()
{
    int i,j;
    scanf("%d",&n);
    sum = 0;
    for(i = 0;i < n;i++)
        scanf("%s",m[i]);
    for(i = 0;i < n;i++)
    {
        for(j = 0;j < n;j++)
        {
            if(m[i][j] == '#')
            {
                if(book[i][j] != 0)
                    continue;
                dfs(i,j);
                sum++;
            }
        }
    }
    for(i = 0;i < n;i++)
    {
        for(j = 0;j < n;j++)
        {
            if(book[i][j] == 2 && m[i][j] == '#')
                sum--;
        }
    }
    printf("%d\n",sum);
    return 0;
}