扫雷(c++题解)

题目描述

扫雷是一种计算机游戏，在世纪年代开始流行，并且仍然包含在某些版本的 Microsoft Windows 操作系统中。

在这个问题中，你正在一个矩形网格上玩扫雷游戏。

最初网格内的所有单元格都呈未打开状态。

其中个不同的单元格中隐藏着个地雷。

其他单元格内不包含地雷。

你可以单击任何单元格将其打开。

如果你点击到的单元格中包含一个地雷，那么游戏就会判定失败。

如果你点击到的单元格内不含地雷，则单元格内将显示一个到之间的数字（包括和），这对应于该单元格的所有相邻单元格中包含地雷的单元格的数量。

如果两个单元格共享一个角或边，则它们是相邻单元格。

另外，如果某个单元格被打开时显示数字，那么它的所有相邻单元格也会以递归方式自动打开。

当所有不含地雷的单元格都被打开时，游戏就会判定胜利。

例如，网格的初始状态可能如下所示（* 表示地雷，而 c 表示第一个点击的单元格）：

复制*..*...**.
....*.....
..c..*....
........*.
..........

被点击的单元格旁边没有地雷，因此当它被打开时显示数字，并且它的个相邻单元也被自动打开，此过程不断继续，最终状态如下：

复制*..*...**.
1112*.....
00012*....
00001111*.
00000001..

此时，仍有不包含地雷的单元格（用 . 字符表示）未被打开，因此玩家必须继续点击未打开的单元格，使游戏继续进行。

你想尽快赢得游戏胜利并希望找到赢得游戏的最低点击次数。

给定网格的尺寸（），输出能够获胜的最小点击次数。

输入格式

第一行包含整数，表示共有组测试数据。

每组数据第一行包含整数，表示游戏网格的尺寸大小。

接下来行，每行包含一个长度为的字符串，字符串由 .（无雷）和 *（有雷）构成，表示游戏网格的初始状态。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为 Case #x: y，其中是组别编号（从开始），是获胜所需的最小点击次数。

数据范围

输入样例：

复制2
3
..*
..*
**.
5
..*..
..*..
.*..*
.*...
.*...

输出样例：

复制Case #1: 2
Case #2: 8

_____________________________________________________________________________

写作不易，点个赞呗!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

_____________________________________________________________________________

#include <bits/stdc++.h>
using namespace std;
int T;
int n;
int ans = 0;
int a[305][305];
bool vis[305][305];
int dir[8][2] = { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, -1 }, { 0, 1 }, { 1, -1 }, { 1, 0 }, { 1, 1 } };
void bfs(int x, int y) {
    queue<pair<int, int> > q;
    q.push({ x, y });
    vis[x][y] = true;
    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 8; i++) {
            int dx = t.first + dir[i][0], dy = t.second + dir[i][1];
            if (dx < 1 || dx > n || dy < 1 || dy > n || a[dx][dy] < 0 || vis[dx][dy])
                continue;
            if (a[dx][dy] == 0) {
                vis[dx][dy] = 1;
                q.push({ dx, dy });
            } else {
                vis[dx][dy] = 1;
            }
        }
    }
}
int main() {
    cin >> T;
    for (int i = 1; i <= T; i++) {
        ans = 0;
        memset(vis, 0, sizeof(vis));
        memset(a, 0, sizeof(a));
        cin >> n;
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                char t;
                cin >> t;
                if (t == '*') {
                    a[j][k] = -INT_MAX;
                    a[j - 1][k - 1]++, a[j - 1][k]++, a[j - 1][k + 1]++, a[j][k - 1]++, a[j][k + 1]++,
                        a[j + 1][k - 1]++, a[j + 1][k]++, a[j + 1][k + 1]++;
                }
            }
        }
        for (int k = 1; k <= n; k++) {
            for (int j = 1; j <= n; j++) {
                if (a[k][j] == 0 && vis[k][j] != 1) {
                    bfs(k, j);
                    ans++;
                }
            }
        }
        for (int k = 1; k <= n; k++) {
            for (int j = 1; j <= n; j++) {
                if (a[k][j] < 0 || vis[k][j])
                    continue;
                ans++;
            }
        }
        cout << "Case #" << i << ": " << ans << endl;
    }
}