本文转载自微信公众号《神奇的程序员K》，作者：神奇的程序员K，转载请联系神奇的程序员K公众号。前言给定一个矩阵和一个字符串，如何从矩阵中找到字符串在矩阵中的路径？本文将与大家分享如何使用回溯法来解决这个问题。欢迎有兴趣的开发者阅读本文。实现思路，我们从题目给出的条件入手，逐步分析思路。矩阵是一个二维数组，字符串可以切割成数组。我们要做的就是依次取出字符串中的每一个字符，判断是否在矩阵中，是否能构成一条完整的路径。比如分析一个已有的矩阵（如下图），有一个字符串bfce，我们需要从矩阵中找出这个字符串在矩阵中的连接路径。abtgcfcsjdeh我们从矩阵的[0][0]位置作为入口开始查找，第一个查找的字符是b：0,0位置的元素是a，与目标值不匹配，继续查找对于位置0,1，位置1的元素为b，与目标值匹配，继续寻找第二个字符f。更新搜索方向，向下搜索。位置1的元素为f，与目标值匹配。继续搜索第三个字符c，并更新搜索方向，往下看，位置2,1的元素为d，与目标值不匹配，返回上一步更新位置1的方向，1、向上查找，已经找到0,0位置的值，返回上一步更新1、1位置的查找方向，向右查找，1、2位置的元素为c，匹配目标值，继续查找第四个字符e，更新查找方向，往下看，位置2的元素，2为e，与目标值匹配，查找所有字符，路径存在且matrix保存找到的元素在矩阵中的index[2,2]position[1,2]position[1,1]position[0,1]position最后路径为：[0][1],[1]][1],[1][2],[2][2]思路分析通过上面的例子，我们可以总结出以下思路：寻找一个切入点，从第一个字符开始寻找它的po矩阵中的位置。进入矩阵后，每一步都会有4个移动方向：下、上、右、左。每移动一个方向，都会判断移动后位置的值是否与当前要查找的位置相同。字符是否相等如果相等，则判断当前位置的元素被访问，继续沿四个移动方向寻找下一个字符；如果没有，则回到上一步的位置点，尝试看其他三个方向是否有匹配重复步骤3，直到所有匹配字符的四个方向都移动完毕。找到字符串中的所有字符后，取出每一步正确的索引位置并保存。四个方向都移动完后，仍然没有找到匹配字符的元素，证明矩阵中不存在该字符串注意：我们在矩阵中找到匹配目标字符的元素后，需要先把元素保存在这个位置，再改成。Use用来表示这个元素已经被访问过，当所有的元素都被找到时，存储的值就会被恢复。分析完实现代码，我们再来看实现代码。代码分为两部分：main函数，用于判断参数规则，找到入口点，返回找到的路径。查找路径函数，用于查找矩阵中的每个字符main函数main函数接受2个参数：路径矩阵和目标字符串。我们需要先判断参数是否为空。遍历矩阵从0,0开始寻找路径。如果找到路径，则返回路径索引，否则返回目标路径不存在的代码。实现如下：exportdefaultclassBacktracking{//目标路径在矩阵中的索引privatereadonlypathIndex:Array;constructor(){this.pathIndex=[];}publicfindMatrixPath(matrix:Array>,target:string):Array{if(target===""){this.pathIndex.push("参数错误：目标路径为空");returnthis.pathIndex;}for(leti=0;i>,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]){returnfalse;}//所有字符都找完整if(index===target.length-1){//保存矩阵中最后一个字符的坐标this.pathIndex.unshift(`[${row}][${col}]`);returntrue;}//保存当前坐标值consttmp=matrix[row][col];//修改当前坐标的值，表示已经找到当前坐标点matrix[row][col]=".";//开始递归：沿查找constres中的当前坐标的四个方向：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;returnres;}完整代码请移步：Backtracking.ts编写测试用例接下来我们将上面的例子代入我们实现的功能来测试是否正确的importBacktrackingfrom"../Backtracking.ts";constpathArr=[["a","b","t","g"],["c","f","c","s"],["j","d","e","h"]];consttarget="bfce";constbacktracking=newBacktracking();constfindResult=backtracking.findMatrixPath(pathArr,target);console.log(`${target}矩阵中的路径索引为`,findResult);执行结果如下：
