扫雷求解器

2024-06-09 21:29| 来源: 网络整理| 查看: 265

给定一个 2D 数组 arr[][]，维度为 N*M，代表扫雷矩阵，其中每个单元格包含一个范围为 [0, 9] 的整数，表示其自身和与其相邻的所有 8 个单元格的地雷数量，任务是解决扫雷器并发现所有地雷矩阵。为包含地雷的单元格打印“X”，为所有其他空单元格打印“_”。如果无法解决扫雷，则打印“-1”。

例子：

输入：arr[][] = {{1, 1, 0, 0, 1, 1, 1}, {2, 3, 2, 1, 1, 2, 2}, {3, 5, 3, 2, 1, 2, 2}, {3, 6, 5, 3, 0, 2, 2}, {2, 4, 3, 2, 0, 1, 1}, {2, 3, 3, 2, 1, 2, 1}, {1, 1, 1, 1, 1, 1, 0}}。输出：_ _ _ _ _ _ _ x _ _ _ _ x _ _ x x _ _ _ x x _ x _ _ _ _ _ x x _ _ _ x _ _ _ _ _ _ _ x _ _ x _ _

输入：arr[][] = {{0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 1}, {0, 0, 0, 0, 0, 1, 1}, {0, 0, 1, 1, 1, 1, 1}, {0, 0, 2, 2, 2, 0, 0}, {0, 0, 2, 2, 2, 0, 0}, {0, 0, 1, 1, 1, 0, 0}}输出：_ _ _ _ _ _ __ _ _ _ _ _ __ _ _ _ _ _ x_ _ _ _ _ _ _ _ x _ _ _ _ _ _ x _ _ _ _ _ _ _ _ _

输入生成：要求解给定的扫雷矩阵 arr[][]，它必须是有效输入，即扫雷矩阵必须是可解的。因此，输入矩阵在 generateMineField() 函数中生成。按照以下步骤生成输入扫雷矩阵：

用于生成输入的输入是雷区 N 和 M 的大小以及雷区的概率 P(或密度)。如果雷区中没有地雷，则概率 P 等于 0；如果雷区中的所有单元格都是地雷，则概率 P 等于 100。为每个单元格选择一个随机数，如果随机数小于P，则将一个地雷分配给网格，一个布尔数组地雷[ ][] 已生成。约束求解器的输入是每个网格的状态，它计算自身的地雷及其周围的八个单元格。

下面是上述方法的实现：

C++ 实现

// C++ program for the above approach #include using namespace std; // Stores the number of rows // and columns of the matrix int N, M; // Stores the final generated input int arr[100][100]; // Direction arrays int dx[9] = { -1, 0, 1, -1, 0, 1, -1, 0, 1 }; int dy[9] = { 0, 0, 0, -1, -1, -1, 1, 1, 1 }; // Function to check if the // cell location is valid bool isValid(int x, int y) { // Returns true if valid return (x >= 0 && y >= 0 && x < N && y < M); } // Function to generate a valid minesweeper // matrix of size ROW * COL with P being // the probability of a cell being a mine void generateMineField(int ROW, int COL, int P) { // Generates the random // number every time srand(time(NULL)); int rand_val; // Stores whether a cell // contains a mine or not int mines[ROW][COL]; // Iterate through each cell // of the matrix mine for (int x = 0; x < ROW; x++) { for (int y = 0; y < COL; y++) { // Generate a random value // from the range [0, 100] rand_val = rand() % 100; // If rand_val is less than P if (rand_val < P) // MArk mines[x][y] as True mines[x][y] = true; // Otherwise, mark // mines[x][y] as False else mines[x][y] = false; } } cout

【本文地址】

公司简介

联系我们