[[411074]]

本文轉載自微信公眾號「神奇的程序員K」，作者神奇的程序員K。轉載本文請聯系神奇的程序員K公眾號。

前言

給定一個矩陣和一個字符串，如何從矩陣中尋找出這個字符串在矩陣中的路徑?本文就跟大家分享下如何使用回溯法來解決這個問題，歡迎各位感興趣的開發者閱讀本文。

實現思路

我們先從題目給出的條件入手，逐步分析得出思路，矩陣就是一個二維數組，字符串可以切割成一個數組，我們要做的就是按順序取出字符串中的每個字符，判斷其是否在矩陣中，能否組成一條完整的路徑出來。

舉例分析

現有一個矩陣(如下所示)，有一個字符串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<string>; 
 
  constructor() { 
    this.pathIndex = []; 
  } 
   
  public findMatrixPath( 
    matrix: Array<Array<string>>, 
    target: string 
  ): Array<string> { 
    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<Array<string>>, 
  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); 

執行結果如下所示：