题解 | #挡住洪水#

#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

int n, m;
vector<string> grid;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void bfs(int start_x, int start_y) {
    if (grid[start_x][start_y] != '0') {
        return;
    }

    queue<pair<int, int>> q;
    q.push({start_x, start_y});
    grid[start_x][start_y] = '#';

    while (!q.empty()) {
        pair<int, int> curr = q.front();
        q.pop();

        for (int i = 0; i < 4; ++i) {
            int nx = curr.first + dx[i];
            int ny = curr.second + dy[i];

            if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == '0') {
                grid[nx][ny] = '#';
                q.push({nx, ny});
            }
        }
    }
}

int main() {
    cin >> n >> m;
    grid.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> grid[i];
    }

    // 1. 从边界开始，淹没所有不安全的 '0' 区域
    for (int j = 0; j < m; ++j) {
        if (grid[0][j] == '0') bfs(0, j);
        if (n > 1 && grid[n - 1][j] == '0') bfs(n - 1, j);
    }
    for (int i = 1; i < n - 1; ++i) {
        if (grid[i][0] == '0') bfs(i, 0);
        if (m > 1 && grid[i][m - 1] == '0') bfs(i, m - 1);
    }

    // 2. 统计图中剩余的 '0' 单元格总数
    int safe_cells = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == '0') {
                safe_cells++;
            }
        }
    }

    cout << safe_cells << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
    static int n, m;
    static char[][] grid;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    public static void bfs(int startX, int startY) {
        if (grid[startX][startY] != '0') {
            return;
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{startX, startY});
        grid[startX][startY] = '#';

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int x = curr[0];
            int y = curr[1];

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == '0') {
                    grid[nx][ny] = '#';
                    queue.offer(new int[]{nx, ny});
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        grid = new char[n][m];
        for (int i = 0; i < n; i++) {
            grid[i] = sc.next().toCharArray();
        }

        // 1. 从边界开始，淹没所有不安全的 '0' 区域
        for (int j = 0; j < m; j++) {
            if (grid[0][j] == '0') bfs(0, j);
            if (n > 1 && grid[n - 1][j] == '0') bfs(n - 1, j);
        }
        for (int i = 1; i < n - 1; i++) {
            if (grid[i][0] == '0') bfs(i, 0);
            if (m > 1 && grid[i][m - 1] == '0') bfs(i, m - 1);
        }

        // 2. 统计图中剩余的 '0' 单元格总数
        int safeCells = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '0') {
                    safeCells++;
                }
            }
        }

        System.out.println(safeCells);
    }
}

import sys
from collections import deque

def solve():
    n_m_str = input()
    n, m = map(int, n_m_str.split())
    grid = [list(input()) for _ in range(n)]

    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    def bfs(start_x, start_y):
        if grid[start_x][start_y] != '0':
            return
        
        q = deque([(start_x, start_y)])
        grid[start_x][start_y] = '#'

        while q:
            x, y = q.popleft()
            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == '0':
                    grid[nx][ny] = '#'
                    q.append((nx, ny))
    
    # 1. 从边界开始，淹没所有不安全的 '0' 区域
    for j in range(m):
        if grid[0][j] == '0':
            bfs(0, j)
        if n > 1 and grid[n - 1][j] == '0':
            bfs(n - 1, j)
    
    for i in range(1, n - 1):
        if grid[i][0] == '0':
            bfs(i, 0)
        if m > 1 and grid[i][m - 1] == '0':
            bfs(i, m - 1)

    # 2. 统计图中剩余的 '0' 单元格总数
    safe_cells = 0
    for r in range(n):
        for c in range(m):
            if grid[r][c] == '0':
                safe_cells += 1
    
    print(safe_cells)

solve()