寻找矩阵中的路径

本文转载自微信公众号「神奇的程序员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,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位置开始寻找路径
  • 路径找到则返回路径索引，否则返回目标路径不存在

代码实现如下：

 
 
 
 
      
  
  
  
  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个参数：路径矩阵、目标字符串、要寻找的行、要寻找的列、要寻找的字符索引

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

代码实现如下：

 
 
 
 
      
  
  
  
  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://www.shufengxianlan.com/qtweb/news36/52436.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

品牌网站建设知识

同城分类信息

电商网站建设　　 　成都app软件开发　　 　移动手机网站制作　　 　企业网站制作　　 　温江服务器托管　　 　发电机组维修保养　　 　吉安网站建设　　 　江油网站建设　　 　网络营销推广　　 　成都网站设计　　 　软文发稿　　 　恒温恒湿空调机组　　 　南充服务器托管　　 　成都标志设计　　 　成都网页设计　　 　眉山服务器租用　　 　崇州搬家公司　　 　雕琢时光茶叶　　 　成都app开发　　 　网站建设费用