×
13518219792

建站动态

根据您的个性需求进行定制 先人一步 抢占小程序红利时代

寻找矩阵中的路径

本文转载自微信公众号「神奇的程序员K」，作者神奇的程序员K。转载本文请联系神奇的程序员K公众号。

甘谷网站建设公司创新互联建站,甘谷网站设计制作，有大型网站制作公司丰富经验。已为甘谷上1000家提供企业网站建设服务。企业网站搭建\成都外贸网站建设公司要多少钱，请找那个售后服务好的甘谷做网站的公司定做！

前言

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

实现思路

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

举例分析

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

 
 
 
 
      
  
  
  
  1. a  b  t  g 
    2.   
  
  
  
  2. c  f  c  s 
    3.   
  
  
  
  3. j  d  e  h 
    4.

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

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

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

思路分析

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

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

实现代码

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

主函数

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

代码实现如下：

 
 
 
 
      
  
  
  
  1. export default class Backtracking { 
    2.   
  
  
  
  2.   // 目标路径在矩阵中的索引 
    3.   
  
  
  
  3.   private readonly pathIndex: Array; 
    4.   
  
  
  
  4.  
    5.   
  
  
  
  5.   constructor() { 
    6.   
  
  
  
  6.     this.pathIndex = []; 
    7.   
  
  
  
  7.   } 
    8.   
  
  
  
  8.    
    9.   
  
  
  
  9.   public findMatrixPath( 
    10.   
  
  
  
  10.     matrix: Array>, 
    11.   
  
  
  
  11.     target: string 
    12.   
  
  
  
  12.   ): Array { 
    13.   
  
  
  
  13.     if (target === "") { 
    14.   
  
  
  
  14.       this.pathIndex.push("参数错误: 目标路径为空"); 
    15.   
  
  
  
  15.       return this.pathIndex; 
    16.   
  
  
  
  16.     } 
    17.   
  
  
  
  17.     for (let i = 0; i < matrix.length; i++) { 
    18.   
  
  
  
  18.       for (let j = 0; j < matrix[i].length; j++) { 
    19.   
  
  
  
  19.         if (this.findPath(matrix, target, i, j, 0)) { 
    20.   
  
  
  
  20.           return this.pathIndex; 
    21.   
  
  
  
  21.         } 
    22.   
  
  
  
  22.       } 
    23.   
  
  
  
  23.     } 
    24.   
  
  
  
  24.     // 未找到 
    25.   
  
  
  
  25.     this.pathIndex.push("目标路径不存在于矩阵中"); 
    26.   
  
  
  
  26.     return this.pathIndex; 
    27.   
  
  
  
  27.   } 
    28.   
  
  
  
  28. } 
    29.

寻找路径函数

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

代码实现如下：

 
 
 
 
      
  
  
  
  1. private findPath( 
    2.   
  
  
  
  2.   matrix: Array>, 
    3.   
  
  
  
  3.   target: string, 
    4.   
  
  
  
  4.   row: number, 
    5.   
  
  
  
  5.   col: number, 
    6.   
  
  
  
  6.   index: number 
    7.   
  
  
  
  7. ): boolean { 
    8.   
  
  
  
  8.   // 边界条件判断 
    9.   
  
  
  
  9.   //  1. 行、列值越界直接返回false 
    10.   
  
  
  
  10.   //  2. matrix[row][col]位置的元素与当前要查找的字符不等，证明这个路径走不通 
    11.   
  
  
  
  11.   if ( 
    12.   
  
  
  
  12.     row >= matrix.length || 
    13.   
  
  
  
  13.     row < 0 || 
    14.   
  
  
  
  14.     col >= matrix[0].length || 
    15.   
  
  
  
  15.     col < 0 || 
    16.   
  
  
  
  16.     matrix[row][col] != target[index] 
    17.   
  
  
  
  17.   ) { 
    18.   
  
  
  
  18.     return false; 
    19.   
  
  
  
  19.   } 
    20.   
  
  
  
  20.   // 所有字符都已查找完成 
    21.   
  
  
  
  21.   if (index === target.length - 1) { 
    22.   
  
  
  
  22.     // 保存最后一个字符在矩阵中的坐标 
    23.   
  
  
  
  23.     this.pathIndex.unshift(`[${row}][${col}]`); 
    24.   
  
  
  
  24.     return true; 
    25.   
  
  
  
  25.   } 
    26.   
  
  
  
  26.   // 保存当前坐标值 
    27.   
  
  
  
  27.   const tmp = matrix[row][col]; 
    28.   
  
  
  
  28.   // 修改当前坐标的值，标识当前坐标点已经被寻找 
    29.   
  
  
  
  29.   matrix[row][col] = "."; 
    30.   
  
  
  
  30.   // 开始递归: 沿着当前坐标的上下左右4个方向查找 
    31.   
  
  
  
  31.   const res: boolean = 
    32.   
  
  
  
  32.     this.findPath(matrix, target, row + 1, col, index + 1) || 
    33.   
  
  
  
  33.     this.findPath(matrix, target, row - 1, col, index + 1) || 
    34.   
  
  
  
  34.     this.findPath(matrix, target, row, col + 1, index + 1) || 
    35.   
  
  
  
  35.     this.findPath(matrix, target, row, col - 1, index + 1); 
    36.   
  
  
  
  36.   // 本轮递归完成，找到了当前要查找字符在矩阵中的位置 
    37.   
  
  
  
  37.   if (res) { 
    38.   
  
  
  
  38.     // 保存当前要查找字符的坐标点 
    39.   
  
  
  
  39.     this.pathIndex.unshift(`[${row}][${col}]`); 
    40.   
  
  
  
  40.   } 
    41.   
  
  
  
  41.   // 递归完成，复原当前坐标 
    42.   
  
  
  
  42.   matrix[row][col] = tmp; 
    43.   
  
  
  
  43.   return res; 
    44.   
  
  
  
  44. } 
    45.

完整代码请移步：Backtracking.ts

编写测试用例

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

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

执行结果如下所示：


网站栏目：寻找矩阵中的路径
文章出自：http://cdbrznjsb.com/article/djcgejo.html

其他资讯

让你的专属顾问为你服务