尋找矩陣中的路徑
本文轉(zhuǎn)載自微信公眾號(hào)「神奇的程序員K」，作者神奇的程序員K。轉(zhuǎn)載本文請(qǐng)聯(lián)系神奇的程序員K公眾號(hào)。
前言
給定一個(gè)矩陣和一個(gè)字符串，如何從矩陣中尋找出這個(gè)字符串在矩陣中的路徑?本文就跟大家分享下如何使用回溯法來(lái)解決這個(gè)問(wèn)題，歡迎各位感興趣的開(kāi)發(fā)者閱讀本文。
實(shí)現(xiàn)思路
我們先從題目給出的條件入手，逐步分析得出思路，矩陣就是一個(gè)二維數(shù)組，字符串可以切割成一個(gè)數(shù)組，我們要做的就是按順序取出字符串中的每個(gè)字符，判斷其是否在矩陣中，能否組成一條完整的路徑出來(lái)。
舉例分析
現(xiàn)有一個(gè)矩陣(如下所示)，有一個(gè)字符串bfce，我們需要從矩陣中找出這個(gè)字符串在矩陣中所連接起來(lái)的路徑。
- a b t g
- c f c s
- j d e h
我們從矩陣的[0][0]位置作為入口開(kāi)始尋找，要查找的第1個(gè)字符為b：
- 0,0 位置的元素是a，與目標(biāo)值不匹配，繼續(xù)尋找0,1位置
- 0,1 位置的元素是是b，與目標(biāo)值匹配，繼續(xù)查找第2個(gè)字符f
- 更新尋找方向，向下查找
- 1,1 位置的元素是f，與目標(biāo)值匹配，繼續(xù)查找第3個(gè)字符c
- 更新尋找方向，向下查找
- 2,1 位置的元素是d，與目標(biāo)值不匹配，回到上一步1,1位置
- 更新尋找方向，向上查找，
- 0,0位置的值已經(jīng)尋找過(guò)了，回到上一步1,1位置
- 更新尋找方向，向右查找
- 1,2 位置的元素是c，與目標(biāo)值匹配，繼續(xù)查找第4個(gè)字符e
- 更新尋找方向，向下查找
- 2,2 位置的元素是e，與目標(biāo)值匹配，所有字符尋找完畢，該路徑存在與矩陣中
保存每一步已找到元素在矩陣中的索引
- [2,2]位置
- [1,2]位置
- [1,1]位置
- [0,1]位置
最終路徑為：[0][1]、[1][1]、[1][2]、[2][2]
思路分析
通過(guò)上述舉例，我們可以總結(jié)出下述思路：
- 尋找一個(gè)切入點(diǎn)，從第一個(gè)字符開(kāi)始尋找其在矩陣中的位置
- 進(jìn)入矩陣后，每一步都會(huì)有4個(gè)移動(dòng)方向：下、上、右、左
- 每移動(dòng)一個(gè)方向，都會(huì)判斷移動(dòng)后位置的值是否與當(dāng)前要查找的字符是否相等
- 如果相等，則標(biāo)識(shí)當(dāng)前位置的元素為已訪問(wèn)狀態(tài)，沿著四個(gè)移動(dòng)方向繼續(xù)尋找下一個(gè)字符
- 如果不相等，則回到上一步的位置點(diǎn)，嘗試其他的三個(gè)方向是否有匹配的元素
- 重復(fù)步驟3，直至所有匹配字符的四個(gè)方向都被移動(dòng)
- 字符串中的全部字符都被找到后，則取出每一步的正確索引位置將其保存起來(lái)
- 四個(gè)方向都被移動(dòng)后，仍未找到與字符所匹配的元素，則證明該字符串不存在于矩陣中
注意：我們?cè)诰仃囍姓业脚c目標(biāo)字符匹配的元素后，我們需要將這個(gè)位置的元素先存起來(lái)，然后再改成. 用于標(biāo)識(shí)這個(gè)元素已經(jīng)訪問(wèn)過(guò)了，當(dāng)所有元素找到后再將存儲(chǔ)起來(lái)的值進(jìn)行還原。
實(shí)現(xiàn)代碼
我們分析出思路后，接下來(lái)我們來(lái)看下實(shí)現(xiàn)代碼，代碼分為2部分：
- 主函數(shù)，用于參數(shù)規(guī)則判斷、尋找切入點(diǎn)、返回找到的路徑
- 尋找路徑函數(shù)，用于在矩陣中尋找每一個(gè)字符
主函數(shù)
主函數(shù)接受2個(gè)參數(shù)：路徑矩陣、目標(biāo)字符串
- 我們需要先對(duì)參數(shù)進(jìn)行判空
- 遍歷矩陣從0,0位置開(kāi)始尋找路徑
- 路徑找到則返回路徑索引，否則返回目標(biāo)路徑不存在
代碼實(shí)現(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ù)錯(cuò)誤: 目標(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個(gè)參數(shù)：路徑矩陣、目標(biāo)字符串、要尋找的行、要尋找的列、要尋找的字符索引
- 首先，我們需要判斷下要尋找的行、列是否超越矩陣的界限
- 矩陣中要尋找的行、列位置的元素與要尋找的字符不相等則直接返回false
- 判斷所有字符是否都查找完成
- 完成的話則存儲(chǔ)行、列索引，返回true
- 未完成則保存當(dāng)前行、列處的值、修改該位置的值為.用于標(biāo)識(shí)為已訪問(wèn)狀態(tài)
- 從當(dāng)前坐標(biāo)點(diǎn)位置沿著其四個(gè)方向：下、上、右、下進(jìn)行查找
- 查找完成后保存已找到字符的坐標(biāo)點(diǎn)，還原當(dāng)前位置所保存的值
代碼實(shí)現(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)前要查找的字符不等，證明這個(gè)路徑走不通
- if (
- row >= matrix.length ||
- row < 0 ||
- col >= matrix[0].length ||
- col < 0 ||
- matrix[row][col] != target[index]
- ) {
- return false;
- }
- // 所有字符都已查找完成
- if (index === target.length - 1) {
- // 保存最后一個(gè)字符在矩陣中的坐標(biāo)
- this.pathIndex.unshift(`[${row}][${col}]`);
- return true;
- }
- // 保存當(dāng)前坐標(biāo)值
- const tmp = matrix[row][col];
- // 修改當(dāng)前坐標(biāo)的值，標(biāo)識(shí)當(dāng)前坐標(biāo)點(diǎn)已經(jīng)被尋找
- matrix[row][col] = ".";
- // 開(kāi)始遞歸: 沿著當(dāng)前坐標(biāo)的上下左右4個(gè)方向查找
- 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;
- }
完整代碼請(qǐng)移步：Backtracking.ts
編寫(xiě)測(cè)試用例
接下來(lái)，我們將上述例子代入我們實(shí)現(xiàn)的函數(shù)中，測(cè)試下是否正確。
- 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);
執(zhí)行結(jié)果如下所示：
