1

以下是我的解决方案,但它只能解决问题。我希望我能看到一些好的解决方案,这些解决方案使用一些动态编程或其他算法(蛮力除外)来尝试将 0 单元格放入板上。

以下是我的算法的步骤:

 set remains = r * c - m.

1) m = 0:都是自由空间。打印 ”。” 在所有单元格中,然后用“c”覆盖任何单元格。

2) 仍然 = 1:同样的想法,. 在所有单元格中打印“*”,然后用“c”覆盖任何单元格。

3)如果r==1,或者c==1:解在前m个单元格中放“*”,在最后一个单元格中放“c”,其他单元格是“.”

(交换案例4)和5的位置)。感谢@TheComputerGuy 的评论。) 4)在其他情况下,如果剩余为 2、3、5、7,则“不可能”。别的:

5) if r==2, or c==2: if m % 2==0, then have solution: in first m/2 columns or rows are "*", and "c" in the last cell,其他单元格是 ”。” 如果 m % 2 == 1,“不可能”。

6)从(0,0)逐行,从左到右,从上到下填充地雷。需要考虑特殊情况:set rs = m / c; cs = m % c 6.1) 如果 rs < r - 2 且 cs < c - 1,则填好,最后一个单元格放“c”,其他单元格为“.”

**********
**********
**********
**********
****……
…………
…………

6.2) 如果 rs < r -3,并且 cs == c -1,则将一个地雷移动到下一行的开头。(这个案例)

**********
**********
**********
*********.(这里不工作)
…………
…………
…………
(最终解决方案)
**********
**********
**********
********..(将*移到下一行并在此处放置一个空格)
*…………
…………
.........C

6.3) 如果 rs == r - 3 和 cs == c -1,则将两个地雷移动到两行的开头

**********
**********
**********
*********.(这里不工作)
…………
…………
(最终解决方案)
**********
**********
**********
*******...(将*移到下一行并在此处放置一个空格)
*…………
*........C

6.4) 如果 rs >= r - 2, 并且保持 % 2 == 0 然后将前两行的第一个保持/2 列留空并用地雷填充其他单元格:

C...******
....******
**********
**********

6.5) 如果 rs >= r - 2,并且保持 %2 == 1,则将前两行的第一个(保持 -3)/2 列留空,将第 3 行的前三列留空,并填充其他有地雷的牢房:

C...******
....******
...**********
**********

现在可以覆盖所有条件。

我是这个系统的新手。如果你真的喜欢我的解决方案,希望能得到一些积分。并欢迎发布您的解决方案。太感谢了!

4

1 回答 1

1

(Posting here because I don't have 10 rep. for the other one)

My solution:

  1. If M = R * C - 1, fill the grid with mines; else:
  2. Recursively "simplify" the grid by filling the last row / column - the smallest of the two - with mines (while you have mines enough to do that).
  3. Put the rest of the mines in the final "simplified" grid, in sequence, starting from the bottom-right. The only constraint here is that you can't leave a single empty cell between a mine and a border.
  4. Click on (0,0).

The C code is here.

于 2014-04-18T18:49:00.670 回答