TypeScript中二维对象数组连通1转2的递归实现需求

嘿，这个问题其实是经典的连通区域遍历场景，递归实现起来特别直观，我来一步步教你写TypeScript代码，包你能搞定！

首先明确需求：我们要在二维数组里找到所有和x直接/间接相邻的1，把它们改成2，同时返回这些需要修改的位置坐标。这里的“相邻”我默认是上下左右四个方向，如果需要支持斜向，后面可以轻松调整。

核心思路 #

1. 先遍历整个二维数组，定位所有x的位置；
2. 对每个x的相邻位置启动递归遍历（深度优先搜索，DFS）；
3. 在递归中，只要遇到未处理的1，就记录它的位置，并继续遍历它的相邻位置，避免重复处理（防止死循环）。

TypeScript 代码实现 #

首先定义一个坐标类型方便记录位置：

type Position = [number, number];

然后是核心函数，包含递归逻辑：

function findAdjacentOnesToConvert(grid: (string | number)[][]): Position[] {
  const rows = grid.length;
  if (rows === 0) return [];
  const cols = grid[0].length;
  const convertedPositions: Position[] = [];
  // 定义四个相邻方向：上、下、左、右（需要斜向的话，加[1,1], [-1,-1], [1,-1], [-1,1]即可）
  const directions: Position[] = [[-1, 0], [1, 0], [0, -1], [0, 1]];

  // 递归遍历函数（DFS）
  const traverse = (row: number, col: number) => {
    // 边界校验：超出数组范围、当前不是1、已经处理过，直接返回
    if (
      row < 0 || row >= rows ||
      col < 0 || col >= cols ||
      grid[row][col] !== 1
    ) {
      return;
    }

    // 记录当前需要修改的位置
    convertedPositions.push([row, col]);
    // 临时把1改成2，避免重复遍历（防止无限递归）
    grid[row][col] = 2;

    // 递归遍历四个方向的相邻位置
    for (const [dr, dc] of directions) {
      traverse(row + dr, col + dc);
    }
  };

  // 遍历整个数组，找到所有x，对每个x的相邻位置启动递归
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] === 'x') {
        // 检查x的四个相邻位置，启动遍历
        for (const [dr, dc] of directions) {
          const newRow = i + dr;
          const newCol = j + dc;
          traverse(newRow, newCol);
        }
      }
    }
  }

  return convertedPositions;
}

代码解释 #

• traverse递归函数：这是核心，每次进入先做边界和有效性检查，符合条件的1会被记录位置，然后标记为2（防止重复处理），再递归检查四个方向的邻居。
• 方向数组：把四个方向存在数组里，用循环遍历，避免重复写四次几乎一样的代码，简洁又易维护。
• 主循环：负责找到所有x的位置，然后触发递归遍历它们的邻居，确保所有和x连通的1都被找到。

示例使用 #

比如用你给出的示例数据（先把一维字符串转成二维数组）：

// 把你的示例字符串转成二维数组（这里假设是单一行的二维数组，根据实际结构调整）
const inputGrid = [
  [1,1,1,1,0,1,1,0,1,1,0,1,0,0,1,1,0,0,'x','x','x','x','x','x',0,0,1,1,0,0,0,0,1,1,0,0,1,0,0,0,0,1,1,1,1,1,1,1]
];

// 获取需要修改的位置
const positionsToConvert = findAdjacentOnesToConvert(inputGrid);
console.log('需要从1改成2的位置：', positionsToConvert);
console.log('修改后的数组：', inputGrid);

可选优化：不修改原数组 #

如果你不想直接修改输入的原数组，可以新增一个visited矩阵来记录已访问的位置，代替直接修改grid的值：

function findAdjacentOnesToConvertNoMutate(grid: (string | number)[][]): Position[] {
  const rows = grid.length;
  if (rows === 0) return [];
  const cols = grid[0].length;
  const convertedPositions: Position[] = [];
  const directions: Position[] = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  // 创建访问标记矩阵，初始都是false
  const visited: boolean[][] = Array(rows).fill(false).map(() => Array(cols).fill(false));

  const traverse = (row: number, col: number) => {
    if (
      row < 0 || row >= rows ||
      col < 0 || col >= cols ||
      grid[row][col] !== 1 ||
      visited[row][col]
    ) {
      return;
    }

    convertedPositions.push([row, col]);
    visited[row][col] = true;

    for (const [dr, dc] of directions) {
      traverse(row + dr, col + dc);
    }
  };

  // 遍历x的逻辑和之前一致
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] === 'x') {
        for (const [dr, dc] of directions) {
          const newRow = i + dr;
          const newCol = j + dc;
          traverse(newRow, newCol);
        }
      }
    }
  }

  return convertedPositions;
}

注意事项 #

如果你的二维数组规模特别大（比如上万行/列），递归可能会触发栈溢出，这时候可以把递归改成迭代式的广度优先搜索（BFS，用队列实现），不过对于大多数常规场景，递归的写法已经足够简单好用了。

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