寻找矩阵中的路径

前言

给定一个矩阵和一个字符串，如何从矩阵中寻找出这个字符串在矩阵中的路径?本文就跟大家分享下如何使用回溯法来解决这个问题，欢迎各位感兴趣的开发者阅读本文。

实现思路

我们先从题目给出的条件入手，逐步分析得出思路，矩阵就是一个二维数组，字符串可以切割成一个数组，我们要做的就是按顺序取出字符串中的每个字符，判断其是否在矩阵中，能否组成一条完整的路径出来。

举例分析

现有一个矩阵(如下所示)，有一个字符串bfce，我们需要从矩阵中找出这个字符串在矩阵中所连接起来的路径。

a  b  t  g 
c  f  c  s 
j  d  e  h 

我们从矩阵的[0][0]位置作为入口开始寻找，要查找的第1个字符为b：

• 0,0 位置的元素是a，与目标值不匹配，继续寻找0,1位置
• 0,1 位置的元素是是b，与目标值匹配，继续查找第2个字符f
  • 更新寻找方向，向下查找
• 1,1 位置的元素是f，与目标值匹配，继续查找第3个字符c
  • 更新寻找方向，向下查找
• 2,1 位置的元素是d，与目标值不匹配，回到上一步1,1位置
  • 更新寻找方向，向上查找，
  • 0,0位置的值已经寻找过了，回到上一步1,1位置
  • 更新寻找方向，向右查找
• 1,2 位置的元素是c，与目标值匹配，继续查找第4个字符e
  
  • 更新寻找方向，向下查找
• 2,2 位置的元素是e，与目标值匹配，所有字符寻找完毕，该路径存在与矩阵中

保存每一步已找到元素在矩阵中的索引

• [2,2]位置
• [1,2]位置
• [1,1]位置
• [0,1]位置

最终路径为：[0][1]、[1][1]、[1][2]、[2][2]

思路分析

通过上述举例，我们可以总结出下述思路：

• 寻找一个切入点，从第一个字符开始寻找其在矩阵中的位置
• 进入矩阵后，每一步都会有4个移动方向：下、上、右、左
• 每移动一个方向，都会判断移动后位置的值是否与当前要查找的字符是否相等
  • 如果相等，则标识当前位置的元素为已访问状态，沿着四个移动方向继续寻找下一个字符
  • 如果不相等，则回到上一步的位置点，尝试其他的三个方向是否有匹配的元素
• 重复步骤3，直至所有匹配字符的四个方向都被移动
  • 字符串中的全部字符都被找到后，则取出每一步的正确索引位置将其保存起来
  • 四个方向都被移动后，仍未找到与字符所匹配的元素，则证明该字符串不存在于矩阵中

注意：我们在矩阵中找到与目标字符匹配的元素后，我们需要将这个位置的元素先存起来，然后再改成. 用于标识这个元素已经访问过了，当所有元素找到后再将存储起来的值进行还原。

实现代码

我们分析出思路后，接下来我们来看下实现代码，代码分为2部分：

• 主函数，用于参数规则判断、寻找切入点、返回找到的路径
• 寻找路径函数，用于在矩阵中寻找每一个字符

主函数

主函数接受2个参数：路径矩阵、目标字符串

• 我们需要先对参数进行判空
• 遍历矩阵从0,0位置开始寻找路径
• 路径找到则返回路径索引，否则返回目标路径不存在

代码实现如下：

export default class Backtracking { 
  // 目标路径在矩阵中的索引 
  private readonly pathIndex: Array; 
 
  constructor() { 
    this.pathIndex = []; 
  } 
   
  public findMatrixPath( 
    matrix: Array>, 
    target: string 
  ): Array { 
    if (target === "") { 
      this.pathIndex.push("参数错误: 目标路径为空"); 
      return this.pathIndex; 
    } 
    for (let i = 0; i < matrix.length; i++) { 
      for (let j = 0; j < matrix[i].length; j++) { 
        if (this.findPath(matrix, target, i, j, 0)) { 
          return this.pathIndex; 
        } 
      } 
    } 
    // 未找到 
    this.pathIndex.push("目标路径不存在于矩阵中"); 
    return this.pathIndex; 
  } 
} 

寻找路径函数

寻找路径函数接受5个参数：路径矩阵、目标字符串、要寻找的行、要寻找的列、要寻找的字符索引

• 首先，我们需要判断下要寻找的行、列是否超越矩阵的界限
• 矩阵中要寻找的行、列位置的元素与要寻找的字符不相等则直接返回false
• 判断所有字符是否都查找完成
  • 完成的话则存储行、列索引，返回true
  • 未完成则保存当前行、列处的值、修改该位置的值为.用于标识为已访问状态
• 从当前坐标点位置沿着其四个方向：下、上、右、下进行查找
• 查找完成后保存已找到字符的坐标点，还原当前位置所保存的值

代码实现如下：

private findPath( 
  matrix: Array>, 
  target: string, 
  row: number, 
  col: number, 
  index: number 
): boolean { 
  // 边界条件判断 
  //  1. 行、列值越界直接返回false 
  //  2. matrix[row][col]位置的元素与当前要查找的字符不等，证明这个路径走不通 
  if ( 
    row >= matrix.length || 
    row < 0 || 
    col >= matrix[0].length || 
    col < 0 || 
    matrix[row][col] != target[index] 
  ) { 
    return false; 
  } 
  // 所有字符都已查找完成 
  if (index === target.length - 1) { 
    // 保存最后一个字符在矩阵中的坐标 
    this.pathIndex.unshift(`[${row}][${col}]`); 
    return true; 
  } 
  // 保存当前坐标值 
  const tmp = matrix[row][col]; 
  // 修改当前坐标的值，标识当前坐标点已经被寻找 
  matrix[row][col] = "."; 
  // 开始递归: 沿着当前坐标的上下左右4个方向查找 
  const res: boolean = 
    this.findPath(matrix, target, row + 1, col, index + 1) || 
    this.findPath(matrix, target, row - 1, col, index + 1) || 
    this.findPath(matrix, target, row, col + 1, index + 1) || 
    this.findPath(matrix, target, row, col - 1, index + 1); 
  // 本轮递归完成，找到了当前要查找字符在矩阵中的位置 
  if (res) { 
    // 保存当前要查找字符的坐标点 
    this.pathIndex.unshift(`[${row}][${col}]`); 
  } 
  // 递归完成，复原当前坐标 
  matrix[row][col] = tmp; 
  return res; 
} 

完整代码请移步：Backtracking.ts

编写测试用例

接下来，我们将上述例子代入我们实现的函数中，测试下是否正确。

import Backtracking from "../Backtracking.ts"; 
 
const pathArr = [ 
  ["a", "b", "t", "g"], 
  ["c", "f", "c", "s"], 
  ["j", "d", "e", "h"] 
]; 
const target = "bfce"; 
const backtracking = new Backtracking(); 
const findResult = backtracking.findMatrixPath(pathArr, target); 
console.log(`${target}在矩阵中的路径索引为`, findResult); 

执行结果如下所示：