题解 | #矩阵中的路径#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix char字符型二维数组
     * @param word string字符串
     * @return bool布尔型
     */
    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        if (matrix == null || word == null || word.length() == 0) {
            return false;
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                boolean[][] flags = new boolean[matrix.length][matrix[0].length];
                boolean result = judge(i, j, matrix, flags, word, 0);
                if (result) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean judge(int i, int j, char[][] matrix, boolean[][]flags,
                         String words, int index) {
        if (index >= words.length()) {
            return true;
        }
        if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length ||
                flags[i][j]) {
            return false;
        }
        flags[i][j] = true;
        if (matrix[i][j] == words.charAt(index)) {
            if (judge(i - 1, j, matrix, flags, words, index + 1)
                    || judge(i + 1, j, matrix, flags, words, index + 1)
                    || judge(i, j + 1, matrix, flags, words, index + 1)
                    || judge(i, j - 1, matrix, flags, words, index + 1)) {
                return true;
            } else {
                flags[i][j] = false;
                return false;
            }
        } else {
            flags[i][j] = false;
            return false;
        }
    }
}

算法思想：

主要的思路是对于每⼀个字符为起点，递归向四周拓展，然后遇到不匹配返回false，匹配则接着匹配直到完成，⾥⾯包含了 回溯 的思想。步骤如下：

针对每⼀个字符为起点，初始化⼀个和矩阵⼀样⼤⼩的标识数组，标识该位置是否被访问过，⼀开始默认是 false 。

1. 如果当前的字符索引已经超过了字符串⻓度，说明前⾯已经完全匹配成功，直接返回 true

2. 如果⾏索引和列索引，不在有效的范围内，或者改位置已经标识被访问，直接返回 false

3. 否则将当前标识置为已经访问过

4. 如果矩阵当前位置的字符和字符串相等，那么就字符串的索引加⼀，递归判断周边的四个，只要⼀个的结果为 true ，就返回 true ，否则将该位置置为没有访问过（相当于回溯，退回上⼀步），返回 false 。矩阵当前位置的字符和字符串不相等，否则同样也是将该位置置为没有访问过（相当于回溯，退回上⼀步），返回 false 。