第一次接触回溯法的题，老实说，看代码的时候是晕晕乎乎的。
进入正题：
1.考虑到从某个格子走到其他格子，还可能回来，再去其他格子，这一个过程可以使用递归，也可以用栈来记录。先使用递归。
2.由于不能重复进入一个格子，所以应该定义一个布尔值，让这个布尔值和格子联系起来。这里是定义一个数组，长度和给的矩阵长度一样，是一维数组。
//这部分思考转换成代码 boolean[] visited = new boolean[matrix.length];
3.因为任意一种元素都可能作为起点，矩阵是二维的，所以利用两层for循环遍历所有元素，每次都调用一次方法，该方法返回以某个位置为起点的情况。
//思考过程转换成代码
for (int j = 0; j < rows; j++) {
for (int i = 0; i < cols; i++) {//每个节点都有可能是起点
if(dfs(matrix,rows,cols,str,i,j,0,visited)) return true;
//这里多了个k=0来充当str的索引，k用来表示在str数组中装了几个字符
}
}4.假如本次使用的是递归。
首先，思考节点走的情况。走了几步，失败，需要回溯，再走。那么每次走就是调用递归，每次回溯就是返回语句，而之前提到，每遍历一个节点，先记录布尔值，然后进入递归，然后回溯时（），需要重置为false。
//思考过程转换成代码 visited[i + j * cols] = true; 递归调用的相关语句 visited[i + j * cols] = false;//这句话是在递归调用的内部，只是此次单独拿出来分析了 //菜是原罪，我之前居然理解的记录的数组只能用二维的 //实际上，一个一维数组就可以表示整个二维数组的情况 //一个3行4列的数组 i + j * cols在表示第三行第四列的位置时，j=2 i=3 cols是列数（4） //其中j是行的索引，i是行的索引，索引第四列导致i=3，第三行导致i=2 //就真的很奇妙，妙不可言。
5.设计判断进入递归的标志，以及递归结束的标志。
当我们标记遍历某个位置，并在visited中进行标记后，就应当考虑进行递归了，由于可以上下左右四个方向移动，因此需要一个'或'操作，也就是说四个操作里面有一个可以递归，那么递归就可以启动。因此在结束本次递归时，应当返回true，所以之前标记的递归写法如下
//递归调用的相关语句
if(dfs(matrix, rows, cols, str, i, j - 1, k + 1, visited) //左移
|| dfs(matrix, rows, cols, str, i + 1, j, k + 1, visited)//下移
|| dfs(matrix, rows, cols, str, i, j + 1, k + 1, visited)//右移
|| dfs(matrix, rows, cols, str, i - 1, j, k + 1, visited))//上移
return true;6.在本次调用递归结束后（成功调用），自然返回true。那么最重要的就是递归结束的情况。
成功的时候，自然应该返回true，此时也不用调用下一次递归，因此这返回true的语句在调用递归之上。同时注意到，怎么样叫成功呢，所以肯定有一个成功的条件作为递归结束的标志。那就是str数组装满了。因此需要设计一个str数组的索引，每次遍历一个元素时，该索引也+1，这里的索引就是方法中的参数k。当k=length-1，就说明到头了。
if(k == str.length - 1) return true; //这句话是成功后的标志，因此这句话应该在下一次递归调用前出现
7.在刚刚的递归调用时，假如失败了，那什么叫做失败呢，并且失败后不应该调用下一次递归，因此这些判断递归结束的语句应该也在递归调用之前，几个边界条件考虑清楚（上下左右不能越界是前4个，布尔数组不为真->为真就走到了重复的格子，以及元素要相等->要和题目给的字符串相等才行啊）
if(i < 0 || i >= cols
|| j < 0 || j >= rows
|| visited[i + j * cols]
|| matrix[i + j * cols] != str[k])
return false;递归结束的标志有了，当告诉上一次递归调用结果为false后，上一次的递归会重置visited数组，重置完后呢，应该返回false表示这一次搜索失败，回溯选择其他方式。
一共有两种情况return false，一个是搜索到头了，提示换一条路，也是终止条件。一个是失败后，递归在层层返回时的return false。同样的有两种return true，一个是递归成功调用后，在层层返回时的return true，一个是成功递归到最深处，完成了一次题目要求的搜索，然后return ture
visited[i + j * cols] = false; return false; //这是层层返回false的情况，每返回一次时，会清除一个visited标记
8.综合起来，大佬的代码就出来了
public class Solution {
public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
if(matrix == null || matrix.length != rows * cols
|| str == null || str.length == 0
|| str.length > matrix.length)
return false;
boolean[] visited = new boolean[matrix.length];
for (int j = 0; j < rows; j++) {
for (int i = 0; i < cols; i++) {//每个节点都有可能是起点
if(dfs(matrix,rows,cols,str,i,j,0,visited)) return true;
}//这里多了个k=0来充当str的索引
}
return false;
}
private boolean dfs(char[] matrix, int rows, int cols, char[] str,
int i, int j, int k, boolean[] visited) {
if(i < 0 || i >= cols || j < 0 || j >= rows ||
visited[i + j * cols] || matrix[i + j * cols] != str[k])
return false;
if(k == str.length - 1) return true;//成功
visited[i + j * cols] = true;
if(dfs(matrix, rows, cols, str, i, j - 1, k + 1, visited)
|| dfs(matrix, rows, cols, str, i + 1, j, k + 1, visited)
|| dfs(matrix, rows, cols, str, i, j + 1, k + 1, visited)
|| dfs(matrix, rows, cols, str, i - 1, j, k + 1, visited))
return true;
visited[i + j * cols] = false;
return false;
}
}思路2 使用栈记录
在看懂递归写法后，这一部分就轻松了很多。每进一次，都把周围合适的点加入到栈，并将对应的标记设为true，并且str+1。退的时候，弹出的元素的标记重置，而str-1。找了一版比较容易看到的非递归写法。
import java.util.Stack;
public class Solution {
private static int col;
public static boolean hasPath(char[] matrix, int rows, int cols, char[] str){
col = cols;
if(matrix.length==0||str.length==0||str.length>matrix.length)
return false;
for (int total = 0; total < matrix.length; total++) {
if (matrix[total] == str[0]) { //只有第一个元素相同时，才调用方法压栈
if (checkpath(matrix, total, str)) return true;
}
}
return false;
}
private static boolean checkpath(char[] matrix, int in, char[] str) {
if(str.length==1) return matrix[in]==str[0];
Stack<Integer> sta = new Stack<Integer>();
sta.push(in);
int k = 1, i, j, index;
int back[] = new int[matrix.length];//使用一个辅助数组
back[in] = 1; //in是传入的位置，将首位置标记置1（back是int数组）
boolean findflag;
while (!sta.empty()) { //栈为空时，一次搜寻结束，只有首元素相同时，才入栈
//这是通过两层for循环控制的
index = sta.peek();
findflag = true;//第一个元素找到了，所以初始的标志true
j=index%col; //j是第几列
i=(index-j)/col; //i是第几行
if ((index - col >= 0) && //上
back[index - col] == 0 &&
matrix[index - col] == str[k]) {
index -= col;
} else if ((index + 1 < (i + 1) * col) &&//右
(back[index + 1]) == 0 &&
matrix[index + 1] == str[k]) {
index += 1;
} else if ((index + col < matrix.length)//下
&& (back[index + col] == 0)
&& matrix[index + col] == str[k]) {
index += col;
} else if ((index - 1 >= i * col) &&//左
(back[index - 1] == 0) &&
matrix[index - 1] == str[k]) {
index -= 1;
} else {
findflag = false;//没有找到
}
if (findflag && back[index] == 0) {
//一个标记上一个元素找到没，一个是下一个元素是否重复查到过。
sta.push(index);
k++;//字符窜str下标推进
if (k == str.length) return true;//已经遍历完str
} else {
sta.pop();
k--;
}
back[index] = 1;//无论有无都标记
}
return false;
}
}总结了一些解题时候的思路，希望下次复习的时候，可以自己独立写出来。
京公网安备 11010502036488号