本文共 1449 字，大约阅读时间需要 4 分钟。

剑指offer12.矩阵中的路径

题目

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

• 示例

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"输出：true输入：board = [["a","b"],["c","d"]], word = "abcd"输出：false

思路和代码

• 思路
  这是一个典型的矩阵搜索的问题，可以用深度优先搜索(DFS递归)+剪枝。
  首先的话每个点都可能是起始点，所以要用一个双层循环来遍历，循环的代码则是对遍历到的点进行深度优先遍历；
  其次在遍历的时候要进行剪枝，先判断不成立的条件：行的左越界、列的左右越界、已经走过被标记的。成立的条件是：遍历的字符的长度为word.length-1(因为K是从0开始的)；中间某个成立后先标记已经遍历过了，再开始上下左右开始进行递归判断，回溯的时候要将标记的字符变为原来的样子，以便进行下一次循环。
• 代码

class Solution {    public boolean exist(char[][] board, String word) {        //DFS+剪枝        char[] words=word.toCharArray();        int n=board.length;        int m=board[0].length;        for (int i = 0; i < n; i++) {            for (int j = 0; j < m; j++) {                if(dfs(board,words,i,j,0))                    return true;            }        }        return false;    }    private static 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,j+1,k+1)                ||dfs(board,word,i-1,j,k+1)||dfs(board,word,i,j-1,k+1);        //开始回溯的时候恢复原样        board[i][j]=word[k];        return res;    }}

转载地址：http://ntgji.baihongyu.com/