如何在KDB及Q语言中遍历M*N网格并计算终点可达路径数

针对你提出的两个KDB/Q相关的网格问题，我来逐一解答：

在KDB/Q中遍历网格，核心是先获取网格的所有坐标或元素，再逐个处理。常见的方式有两种：基于坐标遍历，或者直接遍历矩阵元素。

方式一：基于坐标遍历 #

先生成网格中所有的(x,y)坐标对，再遍历每个坐标进行操作。可以用cross函数快速生成所有坐标组合：

// 定义网格尺寸：M行，N列
M:3; N:3;
// 生成所有坐标（行索引从0到M-1，列索引从0到N-1）
grid_coords: til M cross til N;

// 遍历每个坐标，这里示例是打印坐标
{show "正在处理坐标: ", string x} each grid_coords;

如果需要根据坐标获取网格中的值，假设你有一个M*N的矩阵，可以这样操作：

// 初始化一个3*3的示例网格
grid:(3 3)#1+til 9;  // 结果是：1 2 3; 4 5 6; 7 8 9

// 遍历坐标并取值
{
    x_coord: x[0]; y_coord: x[1];
    show "坐标", string x, "对应的元素值: ", string grid[x_coord; y_coord]
} each grid_coords;

方式二：直接遍历矩阵元素 #

如果你不需要关注坐标，只想遍历所有元素，可以用raze函数将二维矩阵展开为一维列表，再遍历：

// 遍历所有元素并打印
{show "当前元素值: ", string x} each raze grid;

你提到允许向上、向下或斜向移动（这里默认覆盖8个相邻方向：上下左右+四个斜角），计算从起点到终点的所有可能路径数。这类问题需要避免重复访问格子（否则路径会无限多），这里用深度优先搜索（DFS）+ 访问记录的方式实现，逻辑清晰且容易理解。

实现代码 #

// 配置网格参数：行数、列数，起点和终点坐标
rows:3; cols:3;
start:(0;0); end:(2;2);

// 定义8个允许的移动方向：上、下、左、右、左上、右上、左下、右下
directions:(-1 0; 1 0; 0 -1; 0 1; -1 -1; -1 1; 1 -1; 1 1);

// DFS递归函数：参数为当前位置、已访问的格子集合
dfs:{[current_pos; visited]
    // 到达终点，返回1条有效路径
    if[current_pos = end; :1];
    
    // 生成所有可能的下一个位置，并过滤出合法的：在网格内且未被访问
    next_positions: where {
        new_pos: x;
        // 检查是否在网格边界内
        valid_bounds: new_pos[0] >=0 and new_pos[0] < rows and new_pos[1] >=0 and new_pos[1] < cols;
        // 检查是否未被访问过
        not visited: not new_pos in visited;
        valid_bounds and not visited
    } each current_pos + directions;
    
    // 递归计算每个合法下一个位置的路径数，累加总和
    sum dfs[; visited, enlist current_pos] each next_positions
};

// 计算总路径数（初始时已访问集合包含起点）
total_paths: dfs[start; enlist start];
show "从", string start, "到", string end, "的有效路径总数: ", string total_paths;

代码说明 #

1. 方向定义：directions包含了8个相邻方向的偏移量，覆盖所有允许的移动方式。
2. DFS逻辑：每次递归时，先判断是否到达终点；然后生成所有可能的下一步位置，过滤掉超出网格或已访问的格子；最后递归处理每个合法位置，累加所有子路径的数量。
3. 访问记录：用visited集合记录已经走过的格子，避免循环和重复访问，确保每条路径都是唯一的。

如果你的移动方向有特殊限制（比如只能向右、向下、斜下，不能向上/向左），可以改用**动态规划（DP）**来优化性能，避免递归的开销，示例代码如下：

// 限制方向：仅向右(j+1)、向下(i+1)、斜下(i+1,j+1)
target_row:2; target_col:2;

// 初始化DP矩阵，dp[i][j]表示到达(i,j)的路径数
dp:(target_row+1; target_col+1)#0;
dp[0;0]:1;  // 起点路径数为1

// 填充DP矩阵
{
    i:x[0]; j:x[1];
    // 第一行：只能从左侧来
    if[i=0; if[j>0; dp[i;j]+:dp[i;j-1]]];
    // 第一列：只能从上方来
    if[j=0; if[i>0; dp[i;j]+:dp[i-1;j]]];
    // 其他位置：从左上、上方、左侧三个方向累加路径数
    if[i>0; if[j>0; dp[i;j]+:dp[i-1;j] + dp[i;j-1] + dp[i-1;j-1]]]
} each til target_row+1 cross til target_col+1;

show "受限方向下的路径数: ", string dp[target_row; target_col];

内容的提问来源于stack exchange，提问作者RKC