Google Code Jam(2014)资格赛的扫雷大师
收藏

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

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

问题陈述:

《扫雷》是一款电脑游戏,在1980年代开始流行,并且仍然包含在某些版本的Microsoft Windows操作系统中。这个问题有一个相似的想法,但是它不假定您玩过Minesweeper。

在此问题中,您正在相同单元格的网格上玩游戏。每个单元格的内容最初都是隐藏的。网格的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个案例输出文件),因此我猜测它存在一些问题,并且我很确定有更好的解决方案。

最佳答案

算法

Let's first define N, the number of non-mine cells:

N = R * C - M

A simple solution is to fill an area of N non-mine cells line-by-line from top to bottom. Example for R=5, C=5, M=12:

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

那是:

  • Always start in the top-left corner.
  • Fill N / C rows with non-mines from top to bottom.
  • Fill the next line with N % C non-mines from left to right.
  • Fill the rest with mines.

您只需要关心一些特殊情况。

单非矿

If N=1, any configuration is a correct solution.

单行或单列

If R=1, simply fill in the N non-mines from left-to-right. If C=1, fill N rows with a (single) non-mine.

非地雷太少

If N is even, it must be >= 4.

If N is odd, it must be >= 9. Also, R and C must be >= 3.

否则没有解决方案。

无法填充前两行

If N is even and you can't fill at least two rows with non-mines, then fill the first two rows with N / 2 non-mines.

If N is odd and you can't fill at least two rows with non-mines and a third row with 3 non-mines, then fill the first two rows with (N - 3) / 2 non-mines and the third row with 3 non-mines.

最后一行中有一个非地雷

If N % C = 1, move the final non-mine from the last full row to the next row.

Example for R=5, C=5, M=9:

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

摘要

It is possible to write an algorithm that implements these rules and returns a description of the resulting mine field in O(1). Drawing the grid takes O(R*C), of course. I also wrote an implementation in Perl based on these ideas which was accepted by the Code Jam Judge.

    公众号
    关注公众号订阅更多技术干货!