在算法竞赛中，矩阵处理与连通性搜索是常见的基础题型。本文将带你用C++实现经典的扫雷游戏算法，深入掌握八连通搜索与矩阵边界处理的精妙技巧！

问题背景与核心挑战

题目描述

P2670 [NOIP 2015 普及组] 扫雷游戏要求：

• 输入：n×m的雷区矩阵，'*'表示地雷，'?'表示非地雷
• 输出：将'?'替换为周围8个方向的地雷数量，'*'保持不变
• 数据范围：1 ≤ n, m ≤ 100

关键难点分析

1. 八连通搜索：需要检查上下左右及四个对角线方向
2. 边界处理：确保搜索不越出矩阵范围
3. 字符处理：正确进行字符与数字的转换
4. 效率优化：在100×100矩阵中高效完成计算

算法思路解析

核心搜索策略

// 八连通方向向量[6](@ref)[7](@ref)
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

// 检查每个方向的地雷
for (int i = 0; i < 8; i++) {
    int nx = x + dx[i], ny = y + dy[i];
    if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
        if (matrix[nx][ny] == '*') count++;
    }
}

算法流程设计

1. 读取n, m和雷区矩阵
2. 遍历每个格子：
   - 如果是地雷('*')：保持原样
   - 如果是非地雷('?')：统计周围8个方向的地雷数量
3. 输出处理后的矩阵

C++完整实现

#include <iostream>
using namespace std;

const int MAXN = 105;  // 最大行列数（题目限制n, m ≤ 100）

int main() {
    int n, m;
    char matrix[MAXN][MAXN];  // 使用二维字符数组
    
    // 读取输入
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> matrix[i][j];
        }
    }
    
    // 八连通方向数组[6](@ref)
    int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
    int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
    
    // 处理每个格子
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == '*') {
                continue;  // 地雷格保持不变
            }
            
            int count = 0;
            // 八连通搜索[6](@ref)
            for (int k = 0; k < 8; k++) {
                int ni = i + dx[k];
                int nj = j + dy[k];
                // 边界检查[9](@ref)
                if (ni >= 0 && ni < n && nj >= 0 && nj < m) {
                    if (matrix[ni][nj] == '*') {
                        count++;
                    }
                }
            }
            
            // 将数字转换为字符
            matrix[i][j] = '0' + count;
        }
    }
    
    // 输出结果
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << matrix[i][j];
        }
        cout << endl;
    }
    
    return 0;
}

关键知识点深度解析

1.  八连通搜索技巧（⭐⭐⭐⭐⭐）

for (int k = 0; k < 8; k++) {
    int ni = i + dx[k];
    int nj = j + dy[k];
    // 边界检查和处理
}

• 方向完整：覆盖所有8个相邻方向
• 代码简洁：使用预定义方向数组减少重复代码
• 易于维护：修改方向时只需调整数组

2. 边界检查策略（⭐⭐⭐⭐）

if (ni >= 0 && ni < n && nj >= 0 && nj < m)

• 四边界检查：确保不越出矩阵范围
• 索引正确：行索引0~n-1，列索引0~m-1
• 逻辑清晰：使用与运算确保所有条件满足

3. 字符数字转换（⭐⭐⭐）

matrix[i][j] = '0' + count;

• ASCII技巧：利用字符'0'的ASCII码进行转换
• 简洁高效：避免使用字符串流或复杂转换
• 范围安全：count范围0~8，转换结果正确

算法精妙之处

时间复杂度分析

• 矩阵遍历：O(n×m)
• 每个格子搜索：O(8)常数时间
• 总体复杂度：O(8×n×m) = O(n×m)，最优解

空间复杂度优化

• 原地修改：直接在原矩阵上修改，无需额外空间
• 固定大小数组：提前分配足够内存
• 内存高效：适合大规模数据处理

测试用例验证

题目样例验证

输入：
3 3
*??
???
?*?

处理过程：
(0,0): '*' → 保持
(0,1): '?' → 周围有1个雷 → '1'
(0,2): '?' → 周围有0个雷 → '0'
(1,0): '?' → 周围有2个雷 → '2'
(1,1): '?' → 周围有2个雷 → '2'
(1,2): '*' → 保持
(2,0): '?' → 周围有1个雷 → '1'
(2,1): '*' → 保持
(2,2): '?' → 周围有1个雷 → '1'

输出：
*10
221
1*1（符合样例）

边界情况测试

测试场景	矩阵特征	验证要点
最小矩阵	1×1矩阵	单格子处理
全地雷矩阵	所有格子都是'*'	地雷格保持不变
无地雷矩阵	所有格子都是'?'	全0输出
边界测试	地雷在边界	边界检查正确性

常见错误与解决方案

错误1：数组声明错误

// 错误：一维数组用于二维访问
char matrix[101];  // 编译错误：char[int]用作数组下标类型无效
cin >> matrix[i][j];  // 语法错误

解决：使用正确的二维数组声明char matrix[MAXN][MAXN]

错误2：边界检查遗漏

// 错误：忘记边界检查
int ni = i + dx[k], nj = j + dy[k];
if (matrix[ni][nj] == '*') count++; // 可能越界

解决：添加完整的边界条件检查

错误3：方向数组定义错误

// 错误：方向定义不完整或顺序错误
int dx[4] = {-1, 0, 1, 0};  // 只包含四连通，缺少对角线

解决：使用完整的八连通方向数组

算法优化进阶

内存优化版（使用vector）

#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<char>> matrix(n, vector<char>(m));
    
    // 其余逻辑相同
    // ...
}

函数封装版

int countMines(int i, int j, int n, int m, char matrix[MAXN][MAXN]) {
    int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
    int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
    int count = 0;
    
    for (int k = 0; k < 8; k++) {
        int ni = i + dx[k], nj = j + dy[k];
        if (ni >= 0 && ni < n && nj >= 0 && nj < m) {
            if (matrix[ni][nj] == '*') count++;
        }
    }
    return count;
}

性能监控版

#include <chrono>
// 添加性能监控
auto start = chrono::high_resolution_clock::now();
// ... 处理逻辑
auto end = chrono::high_resolution_clock::now();
cout << "处理时间: " << chrono::duration_cast<chrono::milliseconds>(end - start).count() << "ms" << endl;

实际应用拓展

1. 图像处理算法

• 边缘检测：类似八连通的像素邻域分析
• 区域填充：基于连通性的图像处理
• 模式识别：在矩阵中寻找特定模式

2. 游戏开发

• 地图生成：随机生成地雷分布
• AI算法：自动扫雷的智能算法
• 难度调整：根据地雷密度调整游戏难度

3. 科学计算

• 邻域分析：在网格数据中分析局部特征
• 物理模拟：粒子相互作用的邻域计算
• 数据分析：空间数据的局部统计

竞赛技巧总结

数组声明模板

// 对于n×m矩阵（n,m ≤ 100）
const int MAXN = 105;
char matrix[MAXN][MAXN];  // 正确的二维数组声明

八连通搜索模板

int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

for (int k = 0; k < 8; k++) {
    int ni = i + dx[k], nj = j + dy[k];
    if (ni >= 0 && ni < n && nj >= 0 && nj < m) {
        // 处理相邻格子
    }
}

边界检查模板

if (x >= 0 && x < width && y >= 0 && y < height) {
    // 安全访问matrix[y][x]
}

总结与提升

通过这道扫雷游戏题目，我们掌握了：

核心技术要点

1. 二维数组正确使用：声明和访问的语法规范
2. 八连通搜索：矩阵中邻域分析的通用方法
3. 边界处理：确保算法安全性的关键技巧

编程思维提升

"在算法实现中，语法正确性是逻辑正确性的基础。这道题教会我们：语法检查 → 算法设计 → 边界处理 → 测试验证的完整开发流程。"

关键收获：

• 掌握二维数组的正确声明和访问方法
• 理解八连通搜索的完整方向和边界处理
• 学会从编译错误中定位和解决问题

---

   🔥 关注我，解锁CSP-J/S竞赛全攻略 🔥

（每日更新高频考点 + 精选真题解析，助你轻松备赛！）
👇 点击关注 → 立即提升竞赛战力 👇
[https://blog.csdn.net/stillwatersss]

---

📚 专栏亮点抢先看

1. 高频考点突破

   • 每日一题：精选洛谷/LeetCode CSP-J/S经典真题，附详细题解与时间复杂度优化技巧
   • 考点拆解：动态规划、图论、字符串算法等核心专题深度剖析，直击竞赛命题规律
   • 实战模板：限时领取《C++竞赛模板大全》👉 关注后私信回复“模板”获取

2. 备赛效率翻倍技巧

   • 从O(n²)到O(n)：独家算法优化套路，解决TLE超时问题
   • 考场避坑指南：常见失分点分析 + 数据边界处理技巧
   • 互动答疑：评论区留言题目编号，优先解析你的个性化难题

3. 独家福利🌟

   • 粉丝专享：高价值文章设为 “仅粉丝可见”（如《CSP-J/S近5年考点分布与预测》）
   • 资料包：关注后私信 “资料” 领取 竞赛真题库+调试代码工具包

---

💡 为什么值得关注？

✅ 数据驱动：内容基于CSP-J/S真题大数据，命中率超80%
✅ 即学即用：每篇附可运行代码（代码通过洛谷测评）与测试用例
✅ 垂直领域：专注竞赛辅导，拒绝泛技术水文，直击备赛痛点

📢 今日关注福利：前100名新粉丝回复【进阶】赠送《洛谷青铜~黄金段位进阶题库》📘
🔥 行动提示：点击主页 → 专栏 → 开启订阅更新，系统自动推送最新解析！