题目链接

扫雷

题目描述

给定一个 n x m 的初始扫雷矩阵，其中用字符 * 表示雷，用 . 表示空白。请你生成完整的扫雷矩阵。

对于每个非雷格子，需要计算并填写它周围八个方向（上、下、左、右、左上、右上、左下、右下）中雷的总数。如果当前位置是雷，则保持为 *。

输入描述:

  • 第一行输入两个整数 n 和 m，表示矩阵的行数和列数 (1 <= n, m <= 1000)。
  • 接下来 n 行，每行包含 m 个字符（* 或 .），表示初始矩阵。

输出描述:

  • 输出 n 行 m 列，表示完整的扫雷矩阵。
  • 如果原位置是雷，输出 *。
  • 否则输出一个数字，代表周围8个邻格中雷的数量。

示例:

  • 输入: 
    4 4
....
..**
*.*.
.*.*
  • 输出: 
    0122
13**
*4*4
2*3*

解题思路

解决扫雷问题的核心思路是遍历给定的初始矩阵，并根据每个单元格的类型来构建一个新的结果矩阵。

  1. 读取和存储:

    • 首先，读取行数 n 和列数 m。
    • 创建一个 n x m 的二维字符数组（或类似结构）minefield，用于存储输入的初始雷区布局。

  2. 创建结果矩阵:

    • 创建一个新的 n x m 二维字符数组 result_grid，用于存放最终生成的完整扫雷矩阵。

  3. 遍历和计算:

    • 使用两层嵌套循环，遍历 minefield 中的每一个单元格，其坐标为 (i, j)。
    • 对于每个单元格 minefield[i][j]，进行判断：
      • 情况一：如果该位置是雷 (*)
        • 直接将 * 字符复制到结果矩阵的相应位置：result_grid[i][j] = '*'.
      • 情况二：如果该位置是空白 (.)
        • 这是核心计算部分。我们需要检查 (i, j) 周围的8个邻居。
        • 初始化一个计数器 mine_count = 0。
        • 为了方便地检查8个方向，我们可以定义一个方向数组。例如，dx = {-1, -1, -1, 0, 0, 1, 1, 1} 和 dy = {-1, 0, 1, -1, 1, -1, 0, 1} 分别表示8个方向的行和列的偏移量。
        • 遍历这8个方向，对于每个方向 k，计算出邻居的坐标 (ni, nj) = (i + dx[k], j + dy[k])。
        • 边界检查: 在访问邻居 minefield[ni][nj] 之前，必须进行边界检查，确保 0 <= ni < n 且 0 <= nj < m。这是防止数组越界错误的关键步骤。
        • 如果邻居坐标有效，并且 minefield[ni][nj] 是一个雷 (*)，则 mine_count++。
        • 检查完所有8个邻居后，将计数器 mine_count 的值（一个数字）转换为字符，并存入结果矩阵：result_grid[i][j] = (char)(mine_count + '0')。

  4. 打印结果:

    • 当遍历完所有单元格后，result_grid 就构建完成了。
    • 最后，再次遍历 result_grid，并逐行逐字符地将其打印出来。

代码

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

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    // 1. 读取初始雷区
    vector<string> minefield(n);
    for (int i = 0; i < n; ++i) {
        cin >> minefield[i];
    }
    
    // 创建结果矩阵
    vector<vector<char>> result_grid(n, vector<char>(m));
    
    // 定义8个方向的偏移量
    int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
    int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
    
    // 2. 遍历并计算
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (minefield[i][j] == '*') {
                result_grid[i][j] = '*';
            } else {
                int mine_count = 0;
                for (int k = 0; k < 8; ++k) {
                    int ni = i + dx[k];
                    int nj = j + dy[k];
                    
                    // 边界检查
                    if (ni >= 0 && ni < n && nj >= 0 && nj < m) {
                        if (minefield[ni][nj] == '*') {
                            mine_count++;
                        }
                    }
                }
                result_grid[i][j] = (char)(mine_count + '0');
            }
        }
    }
    
    // 3. 打印结果
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << result_grid[i][j];
        }
        cout << endl;
    }
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        char[][] minefield = new char[n][m];
        for (int i = 0; i < n; i++) {
            minefield[i] = sc.next().toCharArray();
        }
        
        char[][] resultGrid = new char[n][m];
        int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
        int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (minefield[i][j] == '*') {
                    resultGrid[i][j] = '*';
                } else {
                    int mineCount = 0;
                    for (int k = 0; k < 8; k++) {
                        int ni = i + dx[k];
                        int nj = j + dy[k];
                        
                        if (ni >= 0 && ni < n && nj >= 0 && nj < m && minefield[ni][nj] == '*') {
                            mineCount++;
                        }
                    }
                    resultGrid[i][j] = (char) (mineCount + '0');
                }
            }
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(resultGrid[i][j]);
            }
            System.out.println();
        }
    }
}

n, m = map(int, input().split())
minefield = [input() for _ in range(n)]
result_grid = [['' for _ in range(m)] for _ in range(n)]

# 8个方向的偏移量
directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]

for i in range(n):
    for j in range(m):
        if minefield[i][j] == '*':
            result_grid[i][j] = '*'
        else:
            mine_count = 0
            for dx, dy in directions:
                ni, nj = i + dx, j + dy
                # 边界检查
                if 0 <= ni < n and 0 <= nj < m and minefield[ni][nj] == '*':
                    mine_count += 1
            result_grid[i][j] = str(mine_count)

for row in result_grid:
    print("".join(row))

算法及复杂度

  • 算法: 网格遍历/模拟。
  • 时间复杂度: 。我们需要遍历 N x M 网格中的每个单元格。对于每个单元格，我们执行常数次操作（检查8个邻居）。
  • 空间复杂度: 。我们需要额外的空间来存储输入的雷区和输出的结果矩阵。