挡住洪水

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
//BFS用队列，c语言没有队列，用数组做一次队列吧，
//思路只要探索到超出边界，说明没有墙，所以就不安全。记录记录这个区域的最大最小行和列，然后看看有没有超出边界就行了。
 
typedef struct{ //坐标的位置
  int x;
  int y; 
} pos;
 
//数组做一次队列
pos queue[250000];
int queue_front=0;  //队头
int queue_end=0;   //队尾
 
//判断队列是不是空的
bool is_empty_queue()
{
    if (queue_front==queue_end) {
        return true;
    }
    return false;
}
 
//入队，队列只能后进先出，返回是否入队成功
bool queue_push(pos temp)
{
    if(queue_end==250000)
    {return false;}
    queue[queue_end]=temp;
    queue_end++;
    return true;
     
}
 
//出队，队列只能后进先出
pos queue_pop()
{
    pos temp=queue[queue_front];
    queue_front++;
    return temp;
}
 
//队列初始化归零
void queue_init(){
    queue_front=0;  //队头
    queue_end=0;   //队尾
}
 
int safe_count=0;//安全区域的数量
char** matrix;
int n,m;//矩阵行和列的长度
//找连通区域
void bfs(int x,int y)//对哦，这个x和y是起点不是头节点的位置
{
    int min_x=x;int max_x=x;int min_y=y;int max_y=y;
    int zero_count = 0;  // 统计这个区域的0的个数
    pos start={.x=x,.y=y};
    matrix[start.x][start.y]='*';  //入队时阻塞，不然等到出队，后面的队会重复进入到这个位置
    queue_push(start);  //初始节点入队列
    bool touch_boundary = false;  // 新增：标记是否接触边界
    zero_count++;
    while (!is_empty_queue()) {  //当头节点不空，取出头节点
        pos temp=queue_pop();
        //matrix[temp.x][temp.y]='*';  //阻塞这个位置不给走
         
        //判断这个点是否超出最小最大行列。
        if (temp.x<min_x) {
            min_x=temp.x;
        }
        if (temp.x>max_x) {
            max_x=temp.x;
        }
        if (temp.y<min_y) {
            min_y=temp.y;
        }
        if (temp.y>max_y) {
            max_y=temp.y;
        }
 
        // 检查是否接触边界
        if (temp.x == 0 || temp.x == n-1 || temp.y == 0 || temp.y == m-1) {
            touch_boundary = true;
        }
 
        //往上下左右探索
        if (temp.x-1>=0&&matrix[temp.x-1][temp.y]=='0') {  //往上探索
            //把这个点加入队列
            pos t={.x=temp.x-1,.y=temp.y};
            matrix[t.x][t.y]='*';
            queue_push(t);
            zero_count++;
        }
        if (temp.x+1<n&&matrix[temp.x+1][temp.y]=='0') {  //往下探索
            //把这个点加入队列
            pos t={.x=temp.x+1,.y=temp.y};
            matrix[t.x][t.y]='*';
            queue_push(t);
            zero_count++;
        }
        if (temp.y-1>=0&&matrix[temp.x][temp.y-1]=='0') {  //往下探索
            //把这个点加入队列
            pos t={.x=temp.x,.y=temp.y-1};
            matrix[t.x][t.y]='*';
            queue_push(t);
            zero_count++;
        }
        if (temp.y+1<m&&matrix[temp.x][temp.y+1]=='0') {  //往下探索
            //把这个点加入队列
            pos t={.x=temp.x,.y=temp.y+1};
            matrix[t.x][t.y]='*';
            queue_push(t);
            zero_count++;
        }
    }
 
    //遍历完看连通区域是否碰到边界
    if (min_x>0&&max_x<n-1&&min_y>0&&max_y<m-1) {
        safe_count+=zero_count;  //安全区域加1
    }
    // 判断安全区域：没有接触任何边界
    // if (!touch_boundary) {
    //     safe_count++;
    // }
}
 
int main() {
    int x,y;
    scanf("%d %d",&x,&y);
    n=x;
    m=y;
    //初始化矩阵
    matrix=malloc(sizeof(char*)*x);
    for (int i=0; i<x; i++) {
        matrix[i]=malloc(sizeof(char)*(y+1));
        scanf("%s",matrix[i]);
        //printf("%s\n",matrix[i]);
    }
 
    //遍历所有所有区域，统计最小最大行和列
    for (int i=0; i<x; i++) {
        for (int j=0; j<y; j++) {
            if (matrix[i][j]=='0') {  //这个位置为0才能走
                queue_init();//队列归零
                bfs(i, j);//以i，j作为起点找连通区域
            }
             
        }
    }
    printf("%d",safe_count);
    return 0;
}