12:矩阵中的路径 12:矩阵中的路径

【12:矩阵中的路径】习惯github pages风格的请看我的另一篇博客
题目12：矩阵中的路径请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中任意一格开始，每一步可以在矩阵中间向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。
举例说明在下面的3*4的矩阵中包含一条字符串bcgkl的路径。
但矩阵中不包含字符串“abcb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二格子之后，路径不能再次进入这个格子。

abcd
efgh
igkl

思路回溯法简介

回溯法适合解决由多个步骤组成的问题，且每个步骤都有多个选项。当在某一步选择了其中一个选项，就进入下一步，然后面临新的选项。如果当前的选项已经确定没有正确答案，就回溯到上一步，在上一步选择另一选项，重复进行。
回溯法的求解过程一般都可以用树状结构表示出来。实现代码很适合用递归完成。

本题用回溯法

寻找
由于回朔法的递归特性，路径可以被开成一个栈。当在矩阵中定位了路径中前n个字符的位置之后，在与第n个字符对应的格子的周围都没有找到第n+1个字符，这个时候只要在路径上回到第n-1个字符，重新定位第n个字符。
当矩阵中坐标为（row,col）的格子和路径字符串中下标为pathLength的字符一样时，从4个相邻的格子(row,col-1),(row-1,col),(row,col+1)以及(row+1,col)中去定位路径字符串中下标为pathLength+1的字符。
回溯
由于路径不能重复进入矩阵的格子，还需要定义和字符矩阵大小一样的布尔值矩阵，用来标识路径是否已经进入每个格子。
如果4个相邻的格子都没有匹配字符串中下标为pathLength+1的字符，表明当前路径字符串中下标为pathLength的字符在矩阵中的定位不正确，我们需要回到前一个字符(pathLength-1)，然后重新定位。
一直重复这个过程，直到路径字符串上所有字符都在矩阵中找到合适的位置。

代码实现

public class _12 { public static boolean hasPath(char[][] matrix,String str) { if(matrix==null||str==null||matrix.length<1||str.length()<1) { return false; } int rows=matrix.length; int cols=matrix[0].length; //辅助数组初始化 boolean[][] visitFlag =new boolean[rows][cols]; for(int row=0; row=str.length()) {//整个字符串完成匹配 return true; } if(row<0||row>=matrix.length||col<0||col>=matrix[0].length) {//匹配失败 return false; }//回溯代码：1.未被访问2.字符匹配 if(!visitFlag[row][col] && matrix[row][col]==str.charAt(strIdx)) { visitFlag[row][col]=true; //被访问标示 boolean res=//順時針左上右下 hasPathCore(matrix,row,col-1,visitFlag,str,strIdx+1)|| hasPathCore(matrix,row-1,col,visitFlag,str,strIdx+1)|| hasPathCore(matrix,row,col+1,visitFlag,str,strIdx+1)|| hasPathCore(matrix,row+1,col,visitFlag,str,strIdx+1); if(res) {//結果对了，跳过后面的标记修改 return true; }else { visitFlag[row][col]=false; return false; } }else { return false; } } public static void main(String[] args) { char[][] matrix= { {'a','b','c','d'}, {'e','f','g','h'}, {'i','j','k','l'}}; System.out.println(hasPath(matrix,"bcgkl")); //true System.out.println(hasPath(matrix,"abcb")); //false } }

输出