题解 | #矩阵中的路径#

很常规的回溯算法题目，注意几个坑。

1. 13行初始条件判空
2. dfs函数中30行的递归成功条件不能和34行的错误退出条件交换，若先判断34行则会报String下标越界错误
3. 注意40行和48等的回溯，因为访问过的位置在当前访问中不能再次访问

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    boolean flag = false;
    public boolean hasPath (char[][] matrix, String word) {
        if(matrix == null || matrix.length == 0 || word == null || word.length() == 0) 
            return false;

        int m = matrix.length;
        int n = matrix[0].length;

        for(int i = 0 ; i < m ; i ++){
            for(int j = 0 ; j < n ; j ++){
                dfs(matrix, i, j ,word, 0 );
                if(flag)
                    return true;
            }
        }
        return false;
    }

    public void  dfs(char[][] matrix, int i , int j ,String word, int idx){
        if(idx == word.length()){
            flag = true;
            return;
        } 
        if(i >= matrix.length || i < 0 ||
           j >= matrix[0].length || j < 0 ||
           matrix[i][j] != word.charAt(idx)) {
            return ;
        }
        //当前位置的char先置为另外的字符
        char c = matrix[i][j];
        matrix[i][j] = '0';
        //四个方向进行回溯
        dfs(matrix , i - 1, j , word ,idx + 1);
        dfs(matrix , i + 1, j , word ,idx + 1);
        dfs(matrix , i, j - 1 , word ,idx + 1);
        dfs(matrix , i, j + 1 , word ,idx + 1);
        //回溯
        matrix[i][j] = c;

    }
}