KDB中如何遍历M*N个网格

Question

Qlang中如何遍历m*n个网格，可以向上遍历，向下遍历，对角遍历。找出有多少种可能到达终点的方法。

喜欢下面：

                  0
                  |
           ------- ------
          |       |       |
      ( 0 1)    (1 1)         (1 0) 
         |         .          |
   ------ -----            ------ -----
  |            |   .      |            |
( 0 1)        (1 0)       ( 1 1)        (2 0)   
.... 
(2 2)        .....................   (2 2)

Answer 1

一种方法是使用 .z.s 递归调用具有不同参数的初始函数并求和以给出路径总数。

f:{
  // When you reach a wall, there is only one way to corner so return valid path
  if[any 1=(x;y);:1];
  // Otherwise spawn 3 paths - one up, one right and one diagonally
  :.z.s[x-1;y] + .z.s[x;y-1] + .z.s[x-1;y-1] 
}

q)f[2;2]
3
q)f[2;3]
5
q)f[3;3]
13

如果您沿着边缘而不是正方形行进，您可以将第一行更改为：

if[any 0=(x;y);:1];

一个封闭形式的解决方案就是找到 Delannoy Number，当你沿着边缘行进时，它可以像这样实现。

d:{
  k:1+min(x;y);
  f:{prd 1+til x};
  comb:{[f;m;n] f[m] div f[n]*f[m-n]}[f];
  (sum/) (2 xexp til k) * prd (x;y) comb/:\: til k
 }

q)d[3;3]
63f

这对于较大的电路板来说要快得多，因为我认为第一个解决方案的复杂性是 O(3^m+n)，而第二个解决方案的复杂性是 O(m*n)

q)\t f[7;7]
13
q)\t f[10;10]
1924
q)\t d[7;7]
0
q)\t d[100;100]
1

KDB中如何遍历M*N个网格

How to traverse M*N grid in KDB

kdb