Google Code Jam（2014）资格赛的扫雷大师

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

``````*..*...**.
....*.....
..c..*....
........*.
..........
``````

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

``````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
``````

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

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

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

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

``````. . . .
. . . .
. . . *
* * * *
``````

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

## 算法

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.

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