网格点上放棋子

northwolves · 发表于 2011-1-14 19:56:08

n=6 --------------------------- 011000 000110 010001 100100 000011 101000

056254628 · 发表于 2011-1-14 20:10:15

能否证明n*n型，最多放棋子为2n。(共线定义为有理数斜率，而不仅仅是45度的斜线)

056254628 · 发表于 2011-1-14 20:12:35

按照12楼的判断标准，10、11楼的答案不对。

mathe · 发表于 2011-1-15 12:27:31

写一个程序解决十几阶的问题应该是没有问题的，可以先穷举看看

mathe · 发表于 2011-1-15 12:38:20

初始化时可以先找出所有包含三格以上的行，记录每个格子所在的行O(n^3)复杂度。然后对每个行使用一个计数器，初始化为0. 然后穷举，每下一个格子，判断所有所在行的计数，如果有某行达到2，则不可放子，不然，测试放子，将所在所有行计数加1。而在退栈时同样将每行计数减1即可。还有一种可以优化的方案是每格格子也保持一个计数，保存被删除行（达到两个子）通过这个格子的数目。这样每一个行达到两个子时，这一行的格子计数都加1. 此外，对于每行每列，保存现在还可以使用格子数目，每一个格子计数从0变成1时，行计数减1，反之，从1到0，行计数加1.如果某行或某列余下格子数小于2，直接淘汰，可以提前剪枝

账号		自动登录	找回密码
密码			欢迎注册

[提问] 网格点上放棋子