选格子问题

northwolves

m*n的格子中选3个连续的格子（允许横连，竖连，斜连），有多少种选法？如图所示：
                                       


4个呢？5个呢？6个呢？

BeerRabbit

暂时的思路：写出所有格子的邻接矩阵。

mathe

递推很简单，固定m,然后设n列的为a(n),先计算a(1),a(2),a(3),然后对于更大的，显然，a(n)-a(n-1)=a(3)-a(2)

northwolves

mathe 发表于 2014-11-16 10:33
递推很简单，固定m,然后设n列的为a(n),先计算a(1),a(2),a(3),然后对于更大的，显然，a(n)-a(n-1)=a(3)-a(2)

m 也得先求出1,2,3吧。是否就是从3*3开始递归？

mathe

其实对每种模式分别计数也可。

northwolves

mathe 发表于 2014-11-18 15:13
其实对每种模式分别计数也可。

如果需要列出结果来，有什么好办法？

3个的还好，5个如何处理呢？发现要么重复计算，要么漏项。

mathe

northwolves 发表于 2014-11-18 20:13
如果需要列出结果来，有什么好办法？

3个的还好，5个如何处理呢？发现要么重复计算，要么漏项。

计算机穷举各种不同排列即可，并没有什么困难的，也不需要什么特殊技巧呀，实在不行5*5的格子里面选择5个，然后淘汰不连续的即可