蓝桥 全球变暖 (bfs)

题目描述
你有一张某海域NxN像素的照片，"."表示海洋、"#"表示陆地，如下所示：

.......
.##....
.##....
....##.
..####.
...###.
.......

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

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

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

.......
.......
.......
.......
....#..
.......
.......

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
输入
第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。

照片保证第1行、第1列、第N行、第N列的像素都是海洋。
输出
一个整数表示答案。
样例输入
7
.......
.##....
.##....
....##.
..####.
...###.
.......
样例输出
1

遍历这个二维图形，对每个点如果是#并且没有访问到就对它bfs，找他所在的联通块。
由于在找联通快时可以把访问过的都book标记，以后可以不用再处理了。
对一个联通块，如果存在上下左右四个都是#符号，那这个联通快就不会消失，nextt数组对上下左右进行扩展，正好就是这种情况。
注意判断是不是#时要放在判断这个点是否符合情况之前，因为只要是#就可以，访问过也没事。这个地方卡了很久。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

int nextt[4][2]={
   {
   0,1},{
   1,0},{
   -1,0},{
   0,-1}};
char maze[1005][1005];
int book[1005][1005];
int n;
typedef struct{
   
    int x, y;
}node;

int bfs(int i, int j){
   
    queue<node> q;
    while (q.size())
        q.pop();
    node t;
    t.x=i, t.y=j;
    q.push(t);
    book[i][j]=1;
    int flag=0;
    while (q.size()){
   
        t = q.front();
        q.pop();
        int dir=0;
        for (int k=0; k<4; k++){
   
            int ti=t.x+nextt[k][0];
            int tj=t.y+nextt[k][1];
            if (maze[ti][tj]=='#')    //有可能已经被访问过,但是只要是#就符合 
                dir++;
            if (book[ti][tj]==1 || maze[ti][tj]=='.')
                continue;
            book[ti][tj]=1;
            node tt;    tt.x=ti, tt.y=tj;
            q.push(tt);
        }
        if (dir==4)
            flag=1;
    }
    return flag;
}
int main(){
   
    scanf("%d", &n);
    for (int i=1; i<=n; i++){
   
        char str[1005];
        scanf("%s", str+1);
        for (int j=1; j<=n; j++){
   
            maze[i][j]=str[j];
        }
    }
    int res = 0;
    for (int i=2; i<=n-1; i++){
   
        for (int j=2; j<=n-1; j++){
   
            if (book[i][j]==0 && maze[i][j]=='#'){
   
                int flag=bfs(i, j);
                if (flag==0)    res++;
            }
        }
    }
    printf("%d", res);
    return 0;
}