全球变暖（bfs）

全球变暖（bfs）

问题描述：有一张某海域n×n像素的照片，“.”代表海洋，“#”代表陆地，其中上下左右四个方向连接诶在一起的一片陆地组成一座岛屿，如图有两篇岛屿。

由于全球变暖海面上升，岛屿边缘像素会被海水淹没，如果一块陆地像素与海洋相邻，就会变淹没，如图，请问有多少岛屿会被完全淹没。

 

思路：此题采用bfs算法，找到每个岛屿的最大连通块，看是否四周都有陆地，有的话就不会被淹没，而被标记过得点就不用再以它为起点寻找连通块了。

代码：

#include
#include
#include
#include
using namespace std;
const int N = 1010;                         /定义像素规模
char mp[N][N];                               /记录像素内容
int vis[N][N];                                   /标记数组，标记是否访问过该点
int flag;                                          /如果四周全为陆地就设为1
int d[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };   /四个方向
void bfs(int x, int y)
{

    queue>q;           /用stl的队列创建存储点（x，y）
    q.push({ x,y });                           /把坐标推进队列
    vis[x][y] = 1;                               /访问过，设为1
    while (q.size()) {
        pair t = q.front();            /取出第一个
        q.pop();                                         /把取出的从队列中d出来
        int tx = t.first, ty = t.second;
        if (mp[tx][ty + 1] == '#'&&mp[tx][ty - 1] == '#'&&            /判断四周是否全为陆地
            mp[tx + 1][ty] == '#'&&mp[tx - 1][ty] == '#')
            flag = 1;
        for (int i = 0; i < 4; i++) {                          /向四周延伸连续块
            int nx = tx + d[i][0], ny = ty + d[i][1];
            if (vis[nx][ny] == 0 && mp[nx][ny] == '#')
            {
                vis[nx][ny] = 1;
                q.push({ nx,ny });
            }
        }

    }
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> mp[i];                     /坐标点输入
    }
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (mp[i][j] == '#'&&vis[i][j] == 0) {
                flag = 0;                                      /用bfs函数找出连接块
                bfs(i, j);
                if (flag == 0)                             /flag为1代表全为陆地不会被湮没，为0就代表会被淹没，并计数
                    ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

俞