基于回溯法的方格网格全路径计数算法故障排查

核心问题点 #

• 错误标记已访问节点
  代码递归前标记的是当前节点start->taken = true，但逻辑上应该标记即将进入的邻居节点neighbour->taken = true。当前节点在进入递归前已经属于路径的一部分，应在初始调用时就标记为已访问，后续递归仅需标记下一个要访问的节点。

• 初始状态未正确设置
  调用paths(start)前，未将起点的taken设为true，也未将path_len初始化为1（起点本身是路径的第一个节点）。这会导致：

  1. 起点可能被重复访问；
  2. 路径长度计数始终少1，触发结束条件时实际未走完所有方格。

• 缺少终点校验逻辑
  当前代码仅通过path_len == n*n-1判断路径完成，但未检查当前节点是否为右下角的终点。即使走完所有方格，若最后停在非终点位置，这条路径是无效的，不应被计入统计。

修正后的核心代码示例 #

// 调用前的初始化操作
start->taken = true;
path_len = 1;
path_count = 0;
paths(start, end_node);

// 修改后的递归函数
void paths(Node* current, Node* end) {
  num_calls++;

  // 仅当路径覆盖所有方格且当前节点是终点时，才计数
  if (path_len == n*n && current == end) {
    path_count++;
    return;
  }
  
  for (Node* neighbour : current->adj) {
    if (!neighbour || neighbour->taken) continue;
    
    // 标记即将访问的邻居为已访问
    neighbour->taken = true;
    path_len++;
    paths(neighbour, end);

    // 回溯：取消标记
    neighbour->taken = false;
    path_len--;
  }
}

说明：修正后增加了终点参数，确保只有走到终点且路径覆盖所有方格时才计数；同时调整了已访问标记的对象，修正了初始状态的逻辑。

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