解题思路

给定一个仅包含 0/1 的矩阵，0 表示平原，1 表示山地。矩阵外全部视为平原（0）。 “盆地”就是被山地在上下左右方向完全包围的平原区域，即这一片 0 的连通块不能与矩阵边界上的平原相连。要求输出所有盆地的平原格子数量之和。

典型做法是 Flood Fill（BFS/DFS 连通块搜索）：

1. 把矩阵中与“外部平原”连通的所有 0 标记掉。

   • 因为矩阵外是平原，我们只要从矩阵四条边上所有的 0 出发，做 BFS/DFS（4 方向），把能到达的 0 都标记为“非盆地平原”。

2. 再次遍历整个矩阵：

   • 对于每一个尚未被标记、且值为 0 的格子，说明它所在的 0 连通块完全被 1 包围，就是一个盆地。
   • 以它为起点再做一次 BFS/DFS，统计这个连通块的大小（0 的个数），累加到答案里。

3. 最终得到的总和即为所有盆地的面积之和。

因为矩阵最大 300×300，使用 BFS/DFS 的时间复杂度 O(NM) 完全可行。

复杂度分析

设矩阵大小为 N×M：

• 时间复杂度：

  • 每个格子在两次 Flood Fill 过程中最多被访问常数次，
  • 整体为 O(NM)。

• 空间复杂度：

  • 需要一个 N×M 的 visited 数组，以及 BFS/DFS 的队列 / 栈，
  • 空间复杂度 O(NM)。

代码实现

Python

import sys
from collections import deque

# 四个方向移动向量：上、下、左、右
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]


def bfs_mark_outside_zero(grid, visited, n, m):
    """从边界上的 0 出发，标记所有与外部平原连通的 0"""
    q = deque()

    # 把四条边上的 0 入队
    for i in range(n):
        # 左边界
        if grid[i][0] == 0 and not visited[i][0]:
            visited[i][0] = True
            q.append((i, 0))
        # 右边界
        if grid[i][m - 1] == 0 and not visited[i][m - 1]:
            visited[i][m - 1] = True
            q.append((i, m - 1))

    for j in range(m):
        # 上边界
        if grid[0][j] == 0 and not visited[0][j]:
            visited[0][j] = True
            q.append((0, j))
        # 下边界
        if grid[n - 1][j] == 0 and not visited[n - 1][j]:
            visited[n - 1][j] = True
            q.append((n - 1, j))

    # BFS 扩展所有与边界 0 连通的 0
    while q:
        x, y = q.popleft()
        for dx, dy in DIRS:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m:
                if grid[nx][ny] == 0 and not visited[nx][ny]:
                    visited[nx][ny] = True
                    q.append((nx, ny))


def bfs_basin_area(grid, visited, n, m, sx, sy):
    """从一个未访问的 0 出发，统计该盆地的面积"""
    q = deque()
    q.append((sx, sy))
    visited[sx][sy] = True
    area = 0

    while q:
        x, y = q.popleft()
        area += 1  # 当前格子属于盆地，面积 +1
        for dx, dy in DIRS:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m:
                if grid[nx][ny] == 0 and not visited[nx][ny]:
                    visited[nx][ny] = True
                    q.append((nx, ny))
    return area


def solve():
    data = list(map(int, sys.stdin.read().split()))
    if not data:
        return
    m, n = data[0], data[1]  # 题面第一行：M N（宽、高）
    grid = []
    idx = 2
    # 读入 N 行，每行 M 个数字（0 或 1）
    for _ in range(n):
        row = data[idx:idx + m]
        grid.append(row)
        idx += m

    visited = [[False] * m for _ in range(n)]

    # 第一步：标记所有与外部连通的 0
    bfs_mark_outside_zero(grid, visited, n, m)

    # 第二步：枚举所有未访问的 0，统计盆地面积之和
    ans = 0
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 0 and not visited[i][j]:
                ans += bfs_basin_area(grid, visited, n, m, i, j)

    print(ans)


if __name__ == "__main__":
    solve()

Java

import java.util.*;

public class Main {

    // 四个方向：上、下、左、右
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    // 从边界上的 0 出发，标记所有与外部平原连通的 0
    static void bfsMarkOutsideZero(int[][] grid, boolean[][] vis, int n, int m) {
        ArrayDeque<int[]> q = new ArrayDeque<>();

        // 左右边界
        for (int i = 0; i < n; i++) {
            if (grid[i][0] == 0 && !vis[i][0]) {
                vis[i][0] = true;
                q.offer(new int[]{i, 0});
            }
            if (grid[i][m - 1] == 0 && !vis[i][m - 1]) {
                vis[i][m - 1] = true;
                q.offer(new int[]{i, m - 1});
            }
        }

        // 上下边界
        for (int j = 0; j < m; j++) {
            if (grid[0][j] == 0 && !vis[0][j]) {
                vis[0][j] = true;
                q.offer(new int[]{0, j});
            }
            if (grid[n - 1][j] == 0 && !vis[n - 1][j]) {
                vis[n - 1][j] = true;
                q.offer(new int[]{n - 1, j});
            }
        }

        // BFS 扩展
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0], y = cur[1];
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    if (grid[nx][ny] == 0 && !vis[nx][ny]) {
                        vis[nx][ny] = true;
                        q.offer(new int[]{nx, ny});
                    }
                }
            }
        }
    }

    // 从某个未访问的 0 出发，统计该盆地的面积
    static int bfsBasinArea(int[][] grid, boolean[][] vis, int n, int m, int sx, int sy) {
        ArrayDeque<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{sx, sy});
        vis[sx][sy] = true;
        int area = 0;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0], y = cur[1];
            area++; // 当前格子属于盆地
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    if (grid[nx][ny] == 0 && !vis[nx][ny]) {
                        vis[nx][ny] = true;
                        q.offer(new int[]{nx, ny});
                    }
                }
            }
        }
        return area;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读入 M N（宽、高）
        if (!sc.hasNextInt()) return;
        int M = sc.nextInt();
        int N = sc.nextInt();

        int[][] grid = new int[N][M];
        // 读入 N 行，每行 M 个 0/1
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                grid[i][j] = sc.nextInt();
            }
        }

        boolean[][] vis = new boolean[N][M];

        // 第一步：标记与外部连通的 0
        bfsMarkOutsideZero(grid, vis, N, M);

        // 第二步：统计所有盆地面积之和
        int ans = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (grid[i][j] == 0 && !vis[i][j]) {
                    ans += bfsBasinArea(grid, vis, N, M, i, j);
                }
            }
        }

        System.out.println(ans);
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 四个方向：上、下、左、右
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

// 从边界上的 0 出发，标记所有与外部平原连通的 0
void bfs_mark_outside_zero(const vector<vector<int>>& grid,
                           vector<vector<bool>>& vis,
                           int n, int m) {
    queue<pair<int, int>> q;

    // 左右边界
    for (int i = 0; i < n; ++i) {
        if (grid[i][0] == 0 && !vis[i][0]) {
            vis[i][0] = true;
            q.push({i, 0});
        }
        if (grid[i][m - 1] == 0 && !vis[i][m - 1]) {
            vis[i][m - 1] = true;
            q.push({i, m - 1});
        }
    }
    // 上下边界
    for (int j = 0; j < m; ++j) {
        if (grid[0][j] == 0 && !vis[0][j]) {
            vis[0][j] = true;
            q.push({0, j});
        }
        if (grid[n - 1][j] == 0 && !vis[n - 1][j]) {
            vis[n - 1][j] = true;
            q.push({n - 1, j});
        }
    }

    // BFS 扩展
    while (!q.empty()) {
        auto cur = q.front(); q.pop();
        int x = cur.first, y = cur.second;
        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                if (grid[nx][ny] == 0 && !vis[nx][ny]) {
                    vis[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
    }
}

// 从某个未访问的 0 出发，统计该盆地的面积
int bfs_basin_area(const vector<vector<int>>& grid,
                   vector<vector<bool>>& vis,
                   int n, int m, int sx, int sy) {
    queue<pair<int, int>> q;
    q.push({sx, sy});
    vis[sx][sy] = true;
    int area = 0;

    while (!q.empty()) {
        auto cur = q.front(); q.pop();
        int x = cur.first, y = cur.second;
        area++; // 当前格子属于盆地
        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                if (grid[nx][ny] == 0 && !vis[nx][ny]) {
                    vis[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
    }
    return area;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int M, N;
    if (!(cin >> M >> N)) return 0; // 读入 M N（宽、高）

    vector<vector<int>> grid(N, vector<int>(M));
    // 读入 N 行，每行 M 个 0/1
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> grid[i][j];
        }
    }

    vector<vector<bool>> vis(N, vector<bool>(M, false));

    // 第一步：标记所有与外部连通的 0
    bfs_mark_outside_zero(grid, vis, N, M);

    // 第二步：统计所有盆地面积之和
    int ans = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (grid[i][j] == 0 && !vis[i][j]) {
                ans += bfs_basin_area(grid, vis, N, M, i, j);
            }
        }
    }

    cout << ans << "\n";
    return 0;
}

题目内容

给定一个表示地图的矩阵,其中$0$表示平原，$1$表示山地。盆地的定义为被山地在水平和垂直方向完全包围的平原

$1$.要求计算盆地的面积，

$2$.矩阵范围之外均为平原

$3$.整个地图中可能包含多个盆地，

输入描述

第$1$行:$M\ N$

• $M$是矩阵的宽，范围是$[1，300]$

• $N$是矩阵的高，范围是$[1,300]$

第$2$到第$N+1$行:$X_1\ X_2...X_M$为矩阵的每行，每个元素的范围是$[0,1]$

输出描述

输出$1$个数字，表示盆地的面积

样例1

输入

7 7
1 1 1 1 1 1 1
1 0 0 0 0 0 1
1 0 1 1 1 0 1
1 0 1 0 1 0 1
1 0 1 1 1 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1

输出

17 

说明

第一行$7\ 7$：表示矩阵的宽和高分别为$7$和$7$ 该矩阵描述的地图中，分别存在两个盆地，其中较小的盆地在较大盆地内部，总面积为$17$ 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 1 1 1 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1

样例2

输入

8 4
1 1 1 0 1 1 1 1 
1 0 1 0 1 1 0 1
1 1 1 0 1 1 1 1
0 0 1 0 0 1 1 1

输出

2

说明

第一行$8\ 4$：表示矩阵的宽和高分别为$8$和$4$ 该矩阵描述的地图中，分别存在两个盆地，其中较小的盆地在较大盆地内部，总面积为$2$ 1 1 1 0 1 1 1 1 1 0 1 0 1 1 0 1

1 1 1 0 1 1 1 1

0 0 1 0 0 1 1 1

样例3

输入

8 4
0 0 1 0 1 0 0 0
0 0 1 0 0 1 0 0
1 1 1 0 0 1 1 1
0 0 0 0 0 0 0 0

输出

0

说明

第一行$8\ 4$：表示矩阵的宽和高分别为$8$和$4$ 矩阵中没有构成闭环的盆地

样例4

输入

8 4
0 0 0 1 1 0 0 0
0 0 1 0 0 1 0 0
0 0 1 0 0 1 0 0
0 0 0 1 1 0 0 0

输出

4

说明

$8\ 4$：表示矩阵$shape$为$8*4$