algorithm - 来自 Google Code Jam(2014)资格赛的扫雷高手

Question

这是 Google Code Jam 资格赛(现已结束)的一道题。如何解决这个问题？

注意:如果您有与答案中讨论的方法不同的方法，请分享它，以便我们扩展我们对解决此问题的不同方法的了解。

Problem Statement:

Minesweeper 是一款在 1980 年代流行的电脑游戏，至今仍包含在某些版本的 Microsoft Windows 操作系统中。本题思路类似，但不假设你玩过扫雷。

在这个问题中，您在相同单元格的网格上玩游戏。每个单元格的内容最初是隐藏的。网格的 M 个不同单元格中隐藏着 M 个地雷。没有其他细胞含有地雷。您可以单击任何单元格以显示它。如果显示的单元格包含地雷，则游戏结束，您输了。否则，显示的单元格将包含一个介于 0 和 8 之间的数字，包括 0 和 8，这对应于包含地雷的相邻单元格的数量。如果两个单元格共享一个角或一条边，则它们是相邻的。此外，如果显示单元格包含 0，则显示单元格的所有邻居也会自动显示，递归地。当所有不包含地雷的单元格都被显示时，游戏结束，您获胜。

例如，棋盘的初始配置可能如下所示('*' 表示地雷，'c' 是第一个点击的单元格):

*..*...**.
....*.....
..c..*....
........*.
..........

点击的单元格附近没有地雷，所以当它被揭开时，它变成 0，它的 8 个相邻单元格也被揭开。此过程继续进行，产生以下板:

*..*...**.
1112*.....
00012*....
00001111*.
00000001..

此时，还有未揭开的不包含地雷的单元格(用'.'字符表示)，因此玩家必须再次点击才能继续游戏。

您想尽快赢得比赛。没有什么比一键获胜更快的了。给定棋盘的大小 (R x C) 和隐藏地雷的数量 M，是否有可能(尽管不太可能)一次点击获胜？您可以选择单击的位置。如果可能，请按照“输出”部分中的规范打印任何有效的地雷配置和您点击的坐标。否则，打印“不可能”。

我尝试过的解决方案:

所以对于解决方案，你需要确保每个非矿节点与其他非矿节点在一个 3x3 矩阵中，或者如果节点在网格的边缘，则为 3x2 或 2x2 矩阵；让我们称之为 0Matrix。所以 0Matrix 中的任何节点都有所有非我的邻居。

首先检查是否需要较少的地雷，或者较少的空节点

if(# mines required < 1/3 of total grid size)
    // Initialize the grid to all clear nodes and populate the mines
    foreach (Node A : the set of non-mine nodes)
        foreach (Node AN : A.neighbors)
            if AN forms a OMatrix with it's neighbors, continue
            else break;
        // If we got here means we can make A a mine since all of it's neighbors 
        // form 0Matricies with their other neighbors
    // End this loop when we've added the number of mines required

else
    // We initialize the grid to all mines and populate the clear nodes
    // Here I handle grids > 3x3; 
    // For smaller grids, I hard coded the logic, eg: 1xn grids, you just populate in 1 dimension

    // Now we know that the # clear nodes required will be 3n+2 or 3n+4
    // eg: if a 4x4 grid need 8 clear nodes : 3(2) + 2

    For (1 -> num 3's needed)
        Add 3 nodes going horizontally
        When horizontal axis is filled, add 3 nodes going vertically
           When vertical axis is filled, go back to horizontal then vertical and so on.

    for(1 -> num 2's needed)
        Add 2 nodes going horizontally or continuing in the direction from above
        When horizontal axis is filled, add 2 nodes going vertically

例如，假设我们有一个需要 8 个干净节点的 4x4 网格，步骤如下:

// Initial grid of all mines
* * * *
* * * *
* * * *
* * * *

// Populating 3's horizontally
. * * *
. * * *
. * * *
* * * *     

. . * *
. . * *
. . * *
* * * *    

// Populating 2's continuing in the same direction as 3's
. . . *
. . . *
. . * *
* * * *        

另一个例子:需要 11 个清晰节点的 4x4 网格；输出:

. . . .
. . . .
. . . *
* * * * 

另一个例子:需要 14 个清晰节点的 4x4 网格；输出:

// Insert the 4 3's horizontally, then switch to vertical to insert the 2's
. . . .
. . . .
. . . .
. . * *  

现在这里我们有一个完全填充的网格，如果我们点击 (0, 0) 就可以一键求解。

我的解决方案适用于大多数情况，但没有通过提交(我确实检查了整个 225 个案例输出文件)，所以我猜它有一些问题，而且我很确定有更好的解决方案.

Answer 1

算法

让我们首先定义N，非地雷单元格的数量:

N = R * C - M

一个简单的解决方案是从上到下逐行填充 N 个非地雷单元格区域。 R=5、C=5、M=12 示例:

c....
.....
...**
*****
*****

即:

• 始终从左上角开始。
• 从上到下用非地雷填充N/C行。
• 从左到右用 N % C 非地雷填充下一行。
• 用地雷填满其余部分。

只有少数特殊情况是您需要关心的。

单非矿

如果N=1，任何配置都是正确的解决方案。

单行或单列

如果 R=1，只需从左到右填写 N 个非地雷。如果 C=1，用(单个)非我的填充 N 行。

非地雷太少

如果 N 是偶数，则它必须 >= 4。

如果 N 是奇数，则它必须 >= 9。此外，R 和 C 必须 >= 3。

否则无解。

无法填写前两行

如果 N 是偶数，并且您不能用非地雷填充至少两行，则用 N/2 非地雷填充前两行。

如果 N 是奇数，并且您不能用非地雷填充至少两行，并且不能用 3 个非地雷填充第三行，则用 (N - 3)/2 非地雷，第三行有 3 个非地雷。

最后一行单个非矿

如果 N % C = 1，将最后一个完整行中的最后一个非地雷移动到下一行。

R=5、C=5、M=9 的示例:

c....
.....
....*
..***
*****

总结

可以编写一个算法来实现这些规则并在 O(1) 中返回对生成的雷区的描述。当然，绘制网格需要 O(R*C)。我还根据这些想法用 Perl 编写了一个实现，并被 Code Jam Judge 接受。