关于java:offer-12-矩阵中的路径-矩阵搜索

矩阵中的门路

典型的 矩阵搜寻问题
深度优先搜寻（DFS）+ 剪枝

题解

本问题是典型的矩阵搜寻问题，可应用 深度优先搜寻（DFS）+ 剪枝 解决。
像是在暴力破解
1、遍历矩阵，找到雷同的字符，
2、从这个字符开始递归上下左右的字符，出界和与 word[k+1] 不等则返回 false；
3、若与 word[k+1]雷同，且 k 是最初一个字符，就示意递归完结且有符合条件的字符串，返回 true。
4、若与 word[k+1]雷同，但不是最初一个字符，就示意须要递归，这里比拟暴力了，
上下左右有一个合乎的，就持续递归上来，没有合乎的就中断并返回 false。从矩阵的下一个字符从新找与 word 的第一个字符雷同的。
这里还有一个重点！！：矩阵中的字符只能用一次，所以须要将判断雷同的字符置为空格字符 '\0'（也就是不能走回头路，如果下一个字母和上一个字母雷同的话，之前那个不为空，就会搜寻到回头路了），那么如果这条路走不通，即第四步其中一个循环返回了 false，就须要复原成原样，返回上一个节点，持续其余方向的循环搜寻。
只有有一条路 true 了，就返回 true，所有的路都走不通了等循环完结了才返回 false。

class Solution {public boolean exist(char[][] board, String word) {char[] words = word.toCharArray();
        for(int i = 0; i < board.length; i++) {for(int j = 0; j < board[0].length; j++) {if(dfs(board, words, i, j, 0)) return true;
            }
        }
        return false;
    }
    boolean dfs(char[][] board, char[] word, int i, int j, int k) {if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
        if(k == word.length - 1) return true;
        board[i][j] = '\0';
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || 
                      dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
        board[i][j] = word[k];
        return res;
    }
}