题目请设计一个函数，判断矩阵中是否存在包含某个字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每走一步可以在矩阵中向左、右、上、下移动一个格子。如果一条路径穿过矩阵的一个单元格，则该路径不能再次进入该单元格。例如，下面的3×4矩阵包含字符串“bfce”的路径（路径中的字母带有下划线）。但是字符串“abfb”的路径并没有包含在矩阵中，因为字符串的第一个字符b占据了矩阵中第一行的第二个格子后，路径就不能再进入这个格子了。ABTGCFCSJDEH思路是先遍历整个矩阵，找到第一个字符，然后上下左右搜索下一个字符。由于每个字符都是相同的判断方式（先判断当前字符是否相等，然后四处查找），所以使用递归函数。由于搜索后不能重复输入字符，因此必须定义一个与字符矩阵大小相同的布尔值矩阵，并将输入的单元格标记为真。如果不满足，则需要回溯。这时候应该把当前位置的布尔值标回false。（所谓回溯无非是标记使用过的字符，处理后去标记）测试用例1.功能测试（多行多列矩阵中路径存在与否）2.边界值测试（矩阵只有一行；矩阵所有字符与路径相同）3.特殊输入测试（null）完整Java代码（含测试代码）/****@Description面试题12：Pathinmatrix**@authoryongh*@date2018911:13:48amonJune16*///题目：请设计一个函数判断矩阵中是否存在包含字符串中所有//字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左、向右、//上下移动一个格子。如果路径穿过矩阵的网格，则该路径不能再次进入//该网格。例如，下面的3×4矩阵包含一个字符串“bfce”的路径（路径中的字母有下划线）。但是字符串“abfb”的路径并没有被包含在矩阵中，因为字符串的第一个//字符b占据了矩阵中第一行的第二个格子，路径无法再次进入这个格子。//ABTG//CFCS//JDEHpublicclassStringPathInMatrix{publicbooleanhasPath(char[]matrix,introws,intcols,char[]str){if(matrix==null||rows<1||cols<1||str==null){返回false;}boolean[]isVisited=newboolean[rows*cols];for(booleanv:isVisited){v=false;}int路径长度=0;for(introw=0;row=行||col>=cols||isVisited[row*cols+col]==true||str[pathLength]!=矩阵[行*列+列])返回假；如果（pathLength==str.length-1）返回真；布尔hasPath=false;isVisited[row*cols+col]=true;hasPath=hasPathCore（矩阵、行、列、行-1、列、海峡、路径长度+1、isVisited）||hasPathCore（矩阵，行，列，行+1，列，海峡，pathLength+1，isVisited）||hasPathCore（矩阵，行，列，行，列-1，海峡，pathLength+1，isVisited）||hasPathCore（矩阵，行，列，行，列+1，海峡，pathLength+1，isVisited）;如果(!hasPath){isVisited[row*cols+col]=false;}返回hasPath；}//=======测试代码========//ABTG//CFCS//JDEH//BFCTBpublicvoidtest1(){char[]matrix="ABTGCFCSJDEH".toCharArray();整数行=3；int列=4;char[]str="BFCTB".toCharArray();如果(!hasPath(matrix,rows,cols,str))System.out.println("测试1通过。");elseSystem.out.println("测试1失败。");}//ABTG//CFCS//JDEH//BFCEpublicvoidtest2(){char[]matrix="ABTGCFCSJDEH".toCharArray();整数行=3；int列=4;char[]str="BFCE".toCharArray();if(hasPath(matrix,rows,cols,str))System.out.println("测试2通过。");elseSystem.out.println("测试2失败。");}//matrix=nullpublicvoidtest3(){char[]matrix=null;整数行=0；int列=0;char[]str="BFCE".toCharArray();if(!hasPath(matrix,rows,cols,str))System.out.println("测试3通过。");elseSystem.out.println("测试3失败。");}//str=nullpublicvoid测试t4(){char[]矩阵="ABTGCFCSJDEH".toCharArray();整数行=3；int列=4;字符[]海峡=空;if(!hasPath(matrix,rows,cols,str))System.out.println("测试4通过。");elseSystem.out.println("测试4失败。");}//A//Apublicvoidtest5(){char[]matrix="A".toCharArray();整数行=1；int列=1;char[]str="A".toCharArray();if(hasPath(matrix,rows,cols,str))System.out.println("测试5通过。");elseSystem.out.println("测试5失败。");}//A//Bpublicvoidtest6(){char[]matrix="A".toCharArray();整数行=1；int列=1;char[]str="B".toCharArray();if(!hasPath(matrix,rows,cols,str))System.out.println("Test6passed.&q不；）；elseSystem.out.println("测试6失败。");}//AAAA//AAAA//AAAA//AAAAAAAAAAAApublicvoidtest7(){char[]矩阵="AAAAAAAAAAAA".toCharArray();整数行=3；int列=4;char[]str="AAAAAAAAAAAA".toCharArray();if(hasPath(matrix,rows,cols,str))System.out.println("测试7通过。");elseSystem.out.println("测试7失败。");}publicstaticvoidmain(String[]args){StringPathInMatrixdemo=newStringPathInMatrix();演示.test1();演示.test2();演示.test3()演示.test4();演示.test5();演示.test6();演示.test7();}}Test1passed.Test2passed.Test3passed.Test4passed.Test5passed.Test6passed.Test7passed.StringPathInMatrix回溯方法用于多步，每步有多个选项：如果当前步满足条件，一个标记给出，当发现下一步不满足条件时，去掉标记2.字符串转字符数组，使用toCharArray()方法3.二维数组下标的计算：row*cols+col，注意不要写错。
