以下是我的解决方案,但它只能解决问题。我希望我能看到一些好的解决方案,这些解决方案使用一些动态编程或其他算法(蛮力除外)来尝试将 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...****** ....****** ...********** **********
现在可以覆盖所有条件。
我是这个系统的新手。如果你真的喜欢我的解决方案,希望能得到一些积分。并欢迎发布您的解决方案。太感谢了!