TypeScript实现findPath路径算法求助及代码验证咨询

题目要求 #

给定二进制矩阵（洞穴地图）、起点坐标begin和终点坐标end，编写findPath函数计算从起点到终点的路径长度，需遵循以下规则：

• 仅能通过值为1的单元格构建路径；
• 每次只能上下或左右移动一格，禁止对角线移动；
• 矩阵边缘不可通行；
• 输入矩阵始终有效，且存在唯一有效路径。

函数原型 #

type Coordinate = [number, number]
type Matrix = number[][]
type FindPathFn = (begin: Coordinate, end: Coordinate, matrix: Matrix) => number 

我的实现代码 #

type Coordinate = [number, number]
type Matrix = number[][]
type FindPathFn = (begin: Coordinate, end: Coordinate, matrix: Matrix) => number

export const findPath: FindPathFn = (begin, end, matrix) => {
  const ROWS = matrix.length;
  const COLS = matrix[0].length;
  const visited = new Array<boolean>(ROWS * COLS).fill(false);

  const dfs = (row: number, col: number, distance: number): number => {
    if (row < 0 || row >= ROWS || col < 0 || col >= COLS || visited[row * COLS + col] || matrix[row][col] !== 1) {
      return -1;
    }

    visited[row * COLS + col] = true;

    if (row === end[0] && col === end[1]) {
      return distance;
    }

    const up = dfs(row - 1, col, distance + 1);
    if (up !== -1) return up;

    const down = dfs(row + 1, col, distance + 1);
    if (down !== -1) return down;

    const left = dfs(row, col - 1, distance + 1);
    if (left !== -1) return left;

    const right = dfs(row, col + 1, distance + 1);
    if (right !== -1) return right;

    return -1;
  };

  return dfs(begin[0], begin[1], 0);
};

代码问题分析与优化建议 #

1. 边缘判断可读性优化：题目明确矩阵边缘不可通行，当前代码的边缘判断逻辑正确，但可以拆分出来单独判断，提升代码可读性：

   // 先判断是否处于矩阵边缘
   if (row === 0 || row === ROWS - 1 || col === 0 || col === COLS - 1) {
     return -1;
   }
   

   （题目已保证输入有效，起点终点不会在边缘，无需额外处理异常情况）

2. DFS回溯逻辑缺失：当前代码标记单元格为已访问后，若该路径走不通，没有重置访问标记。虽然题目保证存在唯一有效路径，当前写法能得到正确结果，但这是DFS的不规范实现——如果后续题目条件变化（比如存在多条路径），代码会直接失效。优化方式是在递归返回后重置标记：

   visited[row * COLS + col] = true;
   
   // ... 原有递归判断逻辑 ...
   
   // 递归返回后重置访问状态，允许其他路径访问（本题虽用不上，但代码更健壮）
   visited[row * COLS + col] = false;
   

3. 路径长度计数确认：当前代码中起点的初始距离为0，每移动一次加1，对应“路径长度为移动步数”的定义。如果题目要求路径长度为经过的单元格总数（起点算1），则需要将初始distance设为1，后续每次移动加1。

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