尋找矩陣中的路徑

作者：神奇的程序員k 2021-07-14 06:40:02

開發(fā) 架構(gòu)

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

[[411074]]

本文轉(zhuǎn)載自微信公眾號「神奇的程序員K」，作者神奇的程序員K。轉(zhuǎn)載本文請聯(lián)系神奇的程序員K公眾號。

前言

實現(xiàn)思路

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

舉例分析

現(xiàn)有一個矩陣(如下所示)，有一個字符串bfce，我們需要從矩陣中找出這個字符串在矩陣中所連接起來的路徑。

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

我們從矩陣的[0][0]位置作為入口開始尋找，要查找的第1個字符為b：

0,0 位置的元素是a，與目標(biāo)值不匹配，繼續(xù)尋找0,1位置
0,1 位置的元素是是b，與目標(biāo)值匹配，繼續(xù)查找第2個字符f
- 更新尋找方向，向下查找
1,1 位置的元素是f，與目標(biāo)值匹配，繼續(xù)查找第3個字符c
- 更新尋找方向，向下查找
2,1 位置的元素是d，與目標(biāo)值不匹配，回到上一步1,1位置
- 更新尋找方向，向上查找，
- 0,0位置的值已經(jīng)尋找過了，回到上一步1,1位置
- 更新尋找方向，向右查找
1,2 位置的元素是c，與目標(biāo)值匹配，繼續(xù)查找第4個字符e
- 更新尋找方向，向下查找
2,2 位置的元素是e，與目標(biāo)值匹配，所有字符尋找完畢，該路徑存在與矩陣中

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

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

最終路徑為：[0][1]、[1][1]、[1][2]、[2][2]

思路分析

通過上述舉例，我們可以總結(jié)出下述思路：

尋找一個切入點(diǎn)，從第一個字符開始尋找其在矩陣中的位置
進(jìn)入矩陣后，每一步都會有4個移動方向：下、上、右、左
每移動一個方向，都會判斷移動后位置的值是否與當(dāng)前要查找的字符是否相等
- 如果相等，則標(biāo)識當(dāng)前位置的元素為已訪問狀態(tài)，沿著四個移動方向繼續(xù)尋找下一個字符
- 如果不相等，則回到上一步的位置點(diǎn)，嘗試其他的三個方向是否有匹配的元素
重復(fù)步驟3，直至所有匹配字符的四個方向都被移動
- 字符串中的全部字符都被找到后，則取出每一步的正確索引位置將其保存起來
- 四個方向都被移動后，仍未找到與字符所匹配的元素，則證明該字符串不存在于矩陣中

注意：我們在矩陣中找到與目標(biāo)字符匹配的元素后，我們需要將這個位置的元素先存起來，然后再改成. 用于標(biāo)識這個元素已經(jīng)訪問過了，當(dāng)所有元素找到后再將存儲起來的值進(jìn)行還原。

實現(xiàn)代碼

我們分析出思路后，接下來我們來看下實現(xiàn)代碼，代碼分為2部分：

主函數(shù)，用于參數(shù)規(guī)則判斷、尋找切入點(diǎn)、返回找到的路徑
尋找路徑函數(shù)，用于在矩陣中尋找每一個字符

主函數(shù)

主函數(shù)接受2個參數(shù)：路徑矩陣、目標(biāo)字符串

我們需要先對參數(shù)進(jìn)行判空
遍歷矩陣從0,0位置開始尋找路徑
路徑找到則返回路徑索引，否則返回目標(biāo)路徑不存在

代碼實現(xiàn)如下：

export default class Backtracking { 
  // 目標(biāo)路徑在矩陣中的索引 
  private readonly pathIndex: Array<string>; 
 
  constructor() { 
    this.pathIndex = []; 
  } 
   
  public findMatrixPath( 
    matrix: Array<Array<string>>, 
    target: string 
  ): Array<string> { 
    if (target === "") { 
      this.pathIndex.push("參數(shù)錯誤: 目標(biāo)路徑為空"); 
      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("目標(biāo)路徑不存在于矩陣中"); 
    return this.pathIndex; 
  } 
}

尋找路徑函數(shù)

尋找路徑函數(shù)接受5個參數(shù)：路徑矩陣、目標(biāo)字符串、要尋找的行、要尋找的列、要尋找的字符索引

首先，我們需要判斷下要尋找的行、列是否超越矩陣的界限
矩陣中要尋找的行、列位置的元素與要尋找的字符不相等則直接返回false
判斷所有字符是否都查找完成
- 完成的話則存儲行、列索引，返回true
- 未完成則保存當(dāng)前行、列處的值、修改該位置的值為.用于標(biāo)識為已訪問狀態(tài)
從當(dāng)前坐標(biāo)點(diǎn)位置沿著其四個方向：下、上、右、下進(jìn)行查找
查找完成后保存已找到字符的坐標(biāo)點(diǎn)，還原當(dāng)前位置所保存的值

代碼實現(xiàn)如下：

private findPath( 
  matrix: Array<Array<string>>, 
  target: string, 
  row: number, 
  col: number, 
  index: number 
): boolean { 
  // 邊界條件判斷 
  //  1. 行、列值越界直接返回false 
  //  2. matrix[row][col]位置的元素與當(dāng)前要查找的字符不等，證明這個路徑走不通 
  if ( 
    row >= matrix.length || 
    row < 0 || 
    col >= matrix[0].length || 
    col < 0 || 
    matrix[row][col] != target[index] 
  ) { 
    return false; 
  } 
  // 所有字符都已查找完成 
  if (index === target.length - 1) { 
    // 保存最后一個字符在矩陣中的坐標(biāo) 
    this.pathIndex.unshift(`[${row}][${col}]`); 
    return true; 
  } 
  // 保存當(dāng)前坐標(biāo)值 
  const tmp = matrix[row][col]; 
  // 修改當(dāng)前坐標(biāo)的值，標(biāo)識當(dāng)前坐標(biāo)點(diǎn)已經(jīng)被尋找 
  matrix[row][col] = "."; 
  // 開始遞歸: 沿著當(dāng)前坐標(biāo)的上下左右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); 
  // 本輪遞歸完成，找到了當(dāng)前要查找字符在矩陣中的位置 
  if (res) { 
    // 保存當(dāng)前要查找字符的坐標(biāo)點(diǎn) 
    this.pathIndex.unshift(`[${row}][${col}]`); 
  } 
  // 遞歸完成，復(fù)原當(dāng)前坐標(biāo) 
  matrix[row][col] = tmp; 
  return res; 
}

完整代碼請移步：Backtracking.ts

編寫測試用例

接下來，我們將上述例子代入我們實現(xiàn)的函數(shù)中，測試下是否正確。

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);