题解 | #矩阵中的路径#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        int n = matrix.length;
        if (0 == n) {
            return false;
        }
        int m = matrix[0].length;
        if (0 == m) {
            return false;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                char chr = matrix[i][j]; // 获取一个字符
                if (chr == word.charAt(0)) {
                    if (process(matrix, word, i, j, 0)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    
    public boolean process(char[][] matrix, String word, int x, int y, int index) {
        if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || index >= word.length() || matrix[x][y] != word.charAt(index)) { // 终止条件
            return false;
        }
        char chr = matrix[x][y]; // 记录当前位置上的字符，便于后续回溯
        matrix[x][y] = '#'; // 赋予当前位置一个特殊字符，表示当前位置已经访问过
        if (index == word.length() - 1) { // 如果此时已经在匹配到最终的位置了，证明已经找到了
            return true;
        }
        boolean u = process(matrix, word, x - 1, y, index + 1);
        boolean d = process(matrix, word, x + 1, y, index + 1);
        boolean l = process(matrix, word, x, y - 1, index + 1);
        boolean r = process(matrix, word, x, y + 1, index + 1);
        matrix[x][y] = chr; // 别忘了进行回溯
        return u || d || l || r;
    }
}