剑指offer12.矩阵中的路径-Toy模板网

这篇具有很好参考价值的文章主要介绍了剑指offer12.矩阵中的路径。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

剑指offer12.矩阵中的路径,剑指offer,矩阵,leetcode,算法

剑指offer12.矩阵中的路径,剑指offer,矩阵,leetcode,算法太难了，想了一会儿没有头绪就直接看了题解。

class Solution {
    public boolean exist(char[][] board, String word) {
       int clowns = board.length;
       int rows = board[0].length;
       boolean[][] visited = new boolean[clowns][rows];
       for(int i =0;i<clowns;i++){
           for(int j=0;j<rows;j++){
             boolean flag = check(board, i, j, 0, visited, word);
             if(flag){
                 return true;
             }
           }
       }
      return false;
    }
    public boolean check(char[][] board, int i, int j, int k,boolean[][] visited, String word){
        if(board[i][j] != word.charAt(k)){
            return false;
        }else if(k == word.length() - 1){
            return true;
        }
        visited[i][j] = true;
        boolean result = false;
        int[][] direction = {{0,1}, {0,-1}, {1,0}, {-1,0}};
        for(int[] dir : direction){
            int newi = i + dir[0]; int newj = j + dir[1];
               if(newi >= 0 & newi < board.length & newj >= 0 & newj < board[0].length){
                if(!visited[newi][newj]){
                 boolean flag = check(board, newi, newj, k+1, visited, word);
                 if(flag){
                     result = true;
                     break;
                 }
            }
          }  
        }
        visited[i][j] = false;
        return result;
    }  
}

题解用的是回溯算法，check(i,j,k)表示从board[i][j]位置开始能否搜索到word第k个字符后面的字串，能搜索到返回true否则返回false。如果board[i][j] != word[k] 返回false。如果相等且是最后一个字符返回true，如果相等但不是最后一个字符，遍历所有相邻位置，如果能搜索到word[k+1]返回true否则返回false。遍历所有位置的[i][j],只要有一个能返回true说明能够找到，否则找不到，其中还要维护一个visited的boolean数组，访问过的元素不能再访问。文章来源地址https://www.toymoban.com/news/detail-540114.html

到了这里，关于剑指offer12.矩阵中的路径的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！