P4961 小埋与扫雷

May 11, 2026 · 10 分钟阅读 · 深度优先搜索模拟 ·

文章目录

题目信息

字段	内容
题号	P4961
难度	普及-
知识点	深度优先搜索、连通块、模拟

题目描述

给定一个 n × m 的扫雷棋盘，1 表示雷，0 表示非雷。请计算这盘扫雷的 3bv（Bechtel’s Board Benchmark Value）。

格子类型定义：

雷：值为 1 的格子
空格：自身不是雷，且周围八格中没有雷的格子
数字：自身不是雷，且周围八格中有雷的格子
空：由"空格"组成的八连通块（一整片相连的空格）

3bv 计算公式：

3bv = "空"的连通块个数 + 周围八格中没有"空格"的"数字"个数

输入格式

第一行：两个整数 n 和 m，表示棋盘大小
后续 n 行：每行有 m 个整数（0 或 1）

输出格式

输出一个整数，表示这盘扫雷的 3bv

样例

输入 #1：

8 8
0 0 0 1 1 0 0 0
1 0 0 1 0 0 0 1
1 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0

输出 #1：

数据范围

1 ≤ n, m ≤ 1000

解题思路

核心思想

本题分三步处理：

标记格子类型：遍历所有未标记的格子（值为 0），检查周围八格是否有雷，分类为"空格"（类型 2）或"数字"（类型 3）
统计空连通块：对所有未访问的"空格"进行 DFS，每次 DFS 代表一个独立的连通块，计数 +1
统计孤立数字：遍历所有"数字"格子，检查周围八格是否有"空格"，如果没有则计数 +1

算法流程

输入棋盘
↓
对每个值为 0 的格子：
  检查周围8格是否有雷 → 标记为空格(2) 或 数字(3)
↓
对每个未访问的空格(2)：
  DFS 标记连通块 → 计数 cnt++
↓
对每个数字格子(3)：
  检查周围8格是否有空格(2) → 若无则 cnt++
↓
输出 cnt

完整代码

C++

#include <bits/stdc++.h>

namespace {

constexpr int kMaxN = 1000;

// 格子类型：0=未标记, 1=雷, 2=空格, 3=数字
int board[kMaxN + 1][kMaxN + 1];
// 访问标记（用于 DFS 连通块）
bool visited[kMaxN + 1][kMaxN + 1];

// 八方向偏移：左上、上、右上、右、右下、下、左下、左
const int kDirY[8] = {-1, -1, -1, 0, 1, 1,  1,  0};
const int kDirX[8] = {-1,  0,  1, 1, 1, 0, -1, -1};

int rows;
int cols;

/**
 * 判断 (y, x) 是空格还是数字，并标记 board[y][x]
 */
void Classify(int y, int x) {
    bool has_mine = false;
    for (int i = 0; i < 8 && !has_mine; ++i) {
        int ny = y + kDirY[i];
        int nx = x + kDirX[i];
        if (ny >= 1 && ny <= rows && nx >= 1 && nx <= cols) {
            if (board[ny][nx] == 1) {
                has_mine = true;
            }
        }
    }
    board[y][x] = has_mine ? 3 : 2;
}

/**
 * DFS 标记从 (y, x) 出发的空格连通块
 */
void DfsMarkRegion(int y, int x) {
    visited[y][x] = true;
    for (int i = 0; i < 8; ++i) {
        int ny = y + kDirY[i];
        int nx = x + kDirX[i];
        if (ny >= 1 && ny <= rows && nx >= 1 && nx <= cols) {
            if (board[ny][nx] == 2 && !visited[ny][nx]) {
                DfsMarkRegion(ny, nx);
            }
        }
    }
}

/**
 * 检查 (y, x) 周围八格是否存在"空格"
 * 返回 true 表示周围没有空格（孤立数字）
 */
bool HasNoAdjacentBlank(int y, int x) {
    for (int i = 0; i < 8; ++i) {
        int ny = y + kDirY[i];
        int nx = x + kDirX[i];
        if (ny >= 1 && ny <= rows && nx >= 1 && nx <= cols) {
            if (board[ny][nx] == 2) {
                return false;
            }
        }
    }
    return true;
}

}  // namespace

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

    std::cin >> rows >> cols;
    for (int i = 1; i <= rows; ++i) {
        for (int j = 1; j <= cols; ++j) {
            std::cin >> board[i][j];
        }
    }

    // 第一步：标记所有非雷格子的类型
    for (int i = 1; i <= rows; ++i) {
        for (int j = 1; j <= cols; ++j) {
            if (board[i][j] == 0) {
                Classify(i, j);
            }
        }
    }

    int result = 0;

    // 第二步：统计空格连通块个数
    for (int i = 1; i <= rows; ++i) {
        for (int j = 1; j <= cols; ++j) {
            if (board[i][j] == 2 && !visited[i][j]) {
                DfsMarkRegion(i, j);
                ++result;
            }
        }
    }

    // 第三步：统计周围无空格的数字格子个数
    for (int i = 1; i <= rows; ++i) {
        for (int j = 1; j <= cols; ++j) {
            if (board[i][j] == 3 && HasNoAdjacentBlank(i, j)) {
                ++result;
            }
        }
    }

    std::cout << result << "\n";
    return 0;
}

Go

package main

import (
    "bufio"
    "fmt"
    "os"
)

const (
    maxN = 1000
)

// 格子类型：0=未标记, 1=雷, 2=空格, 3=数字
var board [maxN + 1][maxN + 1]int
var visited [maxN + 1][maxN + 1]bool

// 八方向偏移
var dirY = [8]int{-1, -1, -1, 0, 1, 1, 1, 0}
var dirX = [8]int{-1, 0, 1, 1, 1, 0, -1, -1}

var rows, cols int

// classify 判断 (y, x) 是空格还是数字，并标记 board
func classify(y, x int) {
    hasMine := false
    for i := 0; i < 8 && !hasMine; i++ {
        ny, nx := y+dirY[i], x+dirX[i]
        if ny >= 1 && ny <= rows && nx >= 1 && nx <= cols {
            if board[ny][nx] == 1 {
                hasMine = true
            }
        }
    }
    if hasMine {
        board[y][x] = 3
    } else {
        board[y][x] = 2
    }
}

// dfsMarkRegion DFS 标记从 (y, x) 出发的空格连通块
func dfsMarkRegion(y, x int) {
    visited[y][x] = true
    for i := 0; i < 8; i++ {
        ny, nx := y+dirY[i], x+dirX[i]
        if ny >= 1 && ny <= rows && nx >= 1 && nx <= cols {
            if board[ny][nx] == 2 && !visited[ny][nx] {
                dfsMarkRegion(ny, nx)
            }
        }
    }
}

// hasNoAdjacentBlank 检查 (y, x) 周围八格是否存在空格
func hasNoAdjacentBlank(y, x int) bool {
    for i := 0; i < 8; i++ {
        ny, nx := y+dirY[i], x+dirX[i]
        if ny >= 1 && ny <= rows && nx >= 1 && nx <= cols {
            if board[ny][nx] == 2 {
                return false
            }
        }
    }
    return true
}

func main() {
    in := bufio.NewReader(os.Stdin)
    fmt.Fscan(in, &rows, &cols)

    for i := 1; i <= rows; i++ {
        for j := 1; j <= cols; j++ {
            fmt.Fscan(in, &board[i][j])
        }
    }

    // 第一步：标记所有非雷格子的类型
    for i := 1; i <= rows; i++ {
        for j := 1; j <= cols; j++ {
            if board[i][j] == 0 {
                classify(i, j)
            }
        }
    }

    result := 0

    // 第二步：统计空格连通块个数
    for i := 1; i <= rows; i++ {
        for j := 1; j <= cols; j++ {
            if board[i][j] == 2 && !visited[i][j] {
                dfsMarkRegion(i, j)
                result++
            }
        }
    }

    // 第三步：统计周围无空格的数字格子个数
    for i := 1; i <= rows; i++ {
        for j := 1; j <= cols; j++ {
            if board[i][j] == 3 && hasNoAdjacentBlank(i, j) {
                result++
            }
        }
    }

    fmt.Println(result)
}

Java

import java.io.*;
import java.util.*;

public class Main {
    private static final int MAX_N = 1000;

    // 格子类型：0=未标记, 1=雷, 2=空格, 3=数字
    private static int[][] board = new int[MAX_N + 1][MAX_N + 1];
    private static boolean[][] visited = new boolean[MAX_N + 1][MAX_N + 1];

    // 八方向偏移
    private static final int[] DIR_Y = {-1, -1, -1, 0, 1, 1,  1,  0};
    private static final int[] DIR_X = {-1,  0,  1, 1, 1, 0, -1, -1};

    private static int rows;
    private static int cols;

    /** 判断 (y, x) 是空格还是数字，并标记 board */
    private static void classify(int y, int x) {
        boolean hasMine = false;
        for (int i = 0; i < 8 && !hasMine; ++i) {
            int ny = y + DIR_Y[i];
            int nx = x + DIR_X[i];
            if (ny >= 1 && ny <= rows && nx >= 1 && nx <= cols) {
                if (board[ny][nx] == 1) hasMine = true;
            }
        }
        board[y][x] = hasMine ? 3 : 2;
    }

    /** DFS 标记从 (y, x) 出发的空格连通块（迭代版本，避免栈溢出） */
    private static void dfsMarkRegion(int startY, int startX) {
        // 使用栈模拟递归
        Deque<int[]> stack = new ArrayDeque<>();
        stack.push(new int[]{startY, startX});
        visited[startY][startX] = true;

        while (!stack.isEmpty()) {
            int[] pos = stack.pop();
            int y = pos[0];
            int x = pos[1];

            for (int i = 0; i < 8; ++i) {
                int ny = y + DIR_Y[i];
                int nx = x + DIR_X[i];
                if (ny >= 1 && ny <= rows && nx >= 1 && nx <= cols) {
                    if (board[ny][nx] == 2 && !visited[ny][nx]) {
                        visited[ny][nx] = true;
                        stack.push(new int[]{ny, nx});
                    }
                }
            }
        }
    }

    /** 检查 (y, x) 周围八格是否存在空格 */
    private static boolean hasNoAdjacentBlank(int y, int x) {
        for (int i = 0; i < 8; ++i) {
            int ny = y + DIR_Y[i];
            int nx = x + DIR_X[i];
            if (ny >= 1 && ny <= rows && nx >= 1 && nx <= cols) {
                if (board[ny][nx] == 2) return false;
            }
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        // 使用 BufferedReader + StringTokenizer，高效且稳定
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        rows = Integer.parseInt(st.nextToken());
        cols = Integer.parseInt(st.nextToken());

        for (int i = 1; i <= rows; ++i) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= cols; ++j) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 第一步：标记所有非雷格子的类型
        for (int i = 1; i <= rows; ++i) {
            for (int j = 1; j <= cols; ++j) {
                if (board[i][j] == 0) classify(i, j);
            }
        }

        int result = 0;

        // 第二步：统计空格连通块个数
        for (int i = 1; i <= rows; ++i) {
            for (int j = 1; j <= cols; ++j) {
                if (board[i][j] == 2 && !visited[i][j]) {
                    dfsMarkRegion(i, j);
                    ++result;
                }
            }
        }

        // 第三步：统计周围无空格的数字格子个数
        for (int i = 1; i <= rows; ++i) {
            for (int j = 1; j <= cols; ++j) {
                if (board[i][j] == 3 && hasNoAdjacentBlank(i, j)) {
                    ++result;
                }
            }
        }

        System.out.println(result);
    }
}

JavaScript

'use strict';

// 格子类型常量
const MINE = 1;    // 雷
const BLANK = 2;   // 空格（周围无雷）
const NUMBER = 3;  // 数字（周围有雷）

// 八方向偏移
const DIR_Y = [-1, -1, -1, 0, 1, 1,  1,  0];
const DIR_X = [-1,  0,  1, 1, 1, 0, -1, -1];

let board;
let visited;
let rows;
let cols;

/**
 * 判断 (y, x) 是空格还是数字，并标记 board
 * @param {number} y
 * @param {number} x
 */
function classify(y, x) {
    let hasMine = false;
    for (let i = 0; i < 8 && !hasMine; i++) {
        const ny = y + DIR_Y[i];
        const nx = x + DIR_X[i];
        if (ny >= 1 && ny <= rows && nx >= 1 && nx <= cols) {
            if (board[ny][nx] === MINE) hasMine = true;
        }
    }
    board[y][x] = hasMine ? NUMBER : BLANK;
}

/**
 * 迭代 DFS 标记从 (y, x) 出发的空格连通块（避免递归栈溢出）
 * @param {number} startY
 * @param {number} startX
 */
function dfsMarkRegion(startY, startX) {
    const stack = [[startY, startX]];
    visited[startY][startX] = true;

    while (stack.length > 0) {
        const [y, x] = stack.pop();
        for (let i = 0; i < 8; i++) {
            const ny = y + DIR_Y[i];
            const nx = x + DIR_X[i];
            if (ny >= 1 && ny <= rows && nx >= 1 && nx <= cols) {
                if (board[ny][nx] === BLANK && !visited[ny][nx]) {
                    visited[ny][nx] = true;
                    stack.push([ny, nx]);
                }
            }
        }
    }
}

/**
 * 检查 (y, x) 周围八格是否存在空格
 * @param {number} y
 * @param {number} x
 * @returns {boolean} 无空格则返回 true
 */
function hasNoAdjacentBlank(y, x) {
    for (let i = 0; i < 8; i++) {
        const ny = y + DIR_Y[i];
        const nx = x + DIR_X[i];
        if (ny >= 1 && ny <= rows && nx >= 1 && nx <= cols) {
            if (board[ny][nx] === BLANK) return false;
        }
    }
    return true;
}

/**
 * 主函数
 */
function main() {
    const input = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split(/\s+/);

    rows = parseInt(input[0], 10);
    cols = parseInt(input[1], 10);

    // 动态创建数组，确保大小正确
    board = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0));
    visited = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(false));

    let idx = 2;
    for (let i = 1; i <= rows; i++) {
        for (let j = 1; j <= cols; j++) {
            board[i][j] = parseInt(input[idx++], 10);
        }
    }

    // 第一步：标记所有非雷格子的类型
    for (let i = 1; i <= rows; i++) {
        for (let j = 1; j <= cols; j++) {
            if (board[i][j] === 0) classify(i, j);
        }
    }

    let result = 0;

    // 第二步：统计空格连通块个数
    for (let i = 1; i <= rows; i++) {
        for (let j = 1; j <= cols; j++) {
            if (board[i][j] === BLANK && !visited[i][j]) {
                dfsMarkRegion(i, j);
                result++;
            }
        }
    }

    // 第三步：统计周围无空格的数字格子个数
    for (let i = 1; i <= rows; i++) {
        for (let j = 1; j <= cols; j++) {
            if (board[i][j] === NUMBER && hasNoAdjacentBlank(i, j)) {
                result++;
            }
        }
    }

    console.log(result);
}

main();

关键代码讲解

1. 格子分类 `classify`

bool has_mine = false;
for (int i = 0; i < 8 && !has_mine; ++i) {
    // 检查周围八格
}
board[y][x] = has_mine ? 3 : 2;

!has_mine 短路求值——一旦发现雷就停止检查，提升效率。

2. DFS 连通块计数

for (int i = 1; i <= rows; ++i) {
    for (int j = 1; j <= cols; ++j) {
        if (board[i][j] == 2 && !visited[i][j]) {
            DfsMarkRegion(i, j);
            ++result;  // 每次 DFS 代表一个独立连通块
        }
    }
}

每次 DFS 会把整片连通的空格全部标记为 visited，所以每个连通块只会进入 DFS 一次。

3. 孤立数字判断 `HasNoAdjacentBlank`

bool HasNoAdjacentBlank(int y, int x) {
    for (int i = 0; i < 8; ++i) {
        if (board[ny][nx] == 2) return false;  // 发现空格则不是孤立数字
    }
    return true;
}

注意这里检查的是空格（类型 2），而不是检查雷。

复杂度分析

方法	时间复杂度	空间复杂度
三步模拟 + DFS	`O(n × m)`	`O(n × m)`

解释：

每个格子最多被访问常数次（分类一次、DFS 标记一次、检查一次）
棋盘大小为 n × m ≤ 10^6，运行很快

易错点

八方向：本题使用八连通，不是四连通，方向数组要包含斜向四格
连通块去重：DFS 后要立即标记 visited，防止同一连通块被重复计数
先分类再 DFS：必须先完成所有格子的类型标记，再进行连通块统计
孤立数字的判断：检查周围是否有空格（类型 2），而非检查是否有雷

类似题目

P1596 Lake Counting（八连通块计数）
P1451 求细胞数量（连通块）
P1141 01迷宫（连通块）