蓝桥杯 全球变暖dfs_上下左右连在一起的一片陆地组成一个岛屿什么意思蓝桥杯

你有一张某海域NxN像素的照片，".“表示海洋、”#"表示陆地，如下所示：
…
.##…
.##…
…##.
…####.
…###.
…
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
…
…
…
…
…#…
…
…

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

【输入格式】
第一行包含一个整数N。 (1 <= N <= 1000)

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

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

【输出格式】

一个整数表示答案

思路：这道题我们其实就是去用dfs去遍历这个数组 遇到上下左右四个方向都为陆地的就说明这在涨潮后还会是陆地 用一个数组记录 涨潮后还会是陆地的坐标 然后就转化成了一个求几块陆地的问题 成了一道dfs板子题

#include<iostream>
using namespace std;
char map[1005][1005];
char vis[1005][1005];
char dd[1005][1005]; //定义了三个数组 vis是判断陆地四周是否为海 始终不变
int x[4] = {1,0,0,-1};  //map是来记录涨潮之后剩下的陆地 有可能一个陆地变成了两个陆地
int y[4] = {0,1,-1,0};  //dd数组用来是dfs函数里面循环可以正常进行
int m;
bool judge(int a,int b)
{
    int ans=0;
    for(int i = 0 ; i < 4 ; i++)
    {
        int nx = a+x[i];
        int ny = b+y[i];
        if(vis[nx][ny]=='#') ans++;
    }
    if(ans==4) return true;
    else return false;
}
void dfs(int a,int b)
{
    for(int i = 0 ; i < 4 ; i++)
    {
        int nx = a+x[i];
        int ny = b+y[i];
        if(nx >=0 && nx<=m && ny>=0 && ny <= m && dd[nx][ny]=='#')
        {
            dd[nx][ny]='.';
            if(!judge(nx,ny))
            {
                map[nx][ny]='.';
                dfs(nx,ny);
            }
        }
    }
}

void dfss(int a,int b)
{
    for(int i = 0 ; i < 4 ; i++)
    {
        int nx = a+x[i];
        int ny = b+y[i];
        if(nx >=0 && nx<=m && ny>=0 && ny <= m && map[nx][ny]=='#')
        {
            map[nx][ny]='.';
        }
    }
}
int main()
{
    cin >> m;
    for(int i=0 ; i <m ; i++)
    {
        cin >> map[i];
        for(int j = 0 ; j < m ; j++)
        {
            vis[i][j]=map[i][j];                //得到标记数组
            dd[i][j]=map[i][j];
        }
    }
    int flag=0;
    for(int i = 0 ; i < m ; i++)
    {
        for(int j = 0 ; j < m ; j++)
        {
            if(dd[i][j] == '#')
            {
                dfs(i,j);
            }
        }
    }
    for(int i = 0 ; i < m ; i++)
    {
        for(int j = 0 ; j < m ; j++）
        {
            if(map[i][j]=='#')
            {
                dfss(i,j);
                flag++;
            }
        }
    }
    cout << flag << endl;
    return 0;
}
/*这个代码让我很开心 代码二十分钟一遍过 没有任何bug 样例也都通过
虽然题很简单 但真的让一个小白在被codeforces摧残了以后有了一点信心 嘤嘤嘤 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

蓝桥杯的题目都相对比较单一 没有什么坑点 唯一需要注意的是一个陆地在涨潮后有可能成为多块陆地