题目描述

image.png
思路：回溯法
视频讲解链接：https://www.bilibili.com/video/BV1XE411J7KD?from=search&seid=13022026484718061702

  1. public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
  2.     {
  3.         char[][] board = new char[rows][cols];
  4.         int x = 0;
  5.         int index = 0;
  6.         for(int i=0;i<matrix.length;i++) {
  7.             if(index>=cols) {
  8.                 index = 0;
  9.                 x++;
  10.             }
  11.             board[x][index] = matrix[i];
  12.             index++;
  13.         }
  14.         StringBuilder word = new StringBuilder();
  15.         for(int i=0;i<str.length;i++) {
  16.             word.append(str[i]);
  17.         }
  18.         return exist(board,word.toString());    
  19.     }
  20.     public boolean exist(char[][] board,String word) {
  21.         boolean[][] vis = new boolean[board.length][board[0].length];
  22.         for(int i=0;i<board.length;i++) {
  23.             for(int j=0;j<board[0].length;j++) {
  24.                 if(solve(board,word,i,j,vis,0)) {
  25.                     return true;
  26.                 }
  27.             }
  28.         }
  29.         return false;
  30.     }
  31.     private boolean solve(char[][] board, String word, int x, int y, boolean[][] vis,int index) {
  32.         if(x<0||x>=board.length||y<0||y>=board[0].length||vis[x][y])
  33.             return false;
  34.         if(word.charAt(index)!=board[x][y])
  35.             return false;
  36.         if(index==word.length()-1)
  37.             return true;
  38.         vis[x][y] = true;
  39.         boolean flag =  solve(board, word, x+1, y, vis,index+1)||
  40.                         solve(board, word, x-1, y, vis,index+1)||
  41.                         solve(board, word, x, y+1, vis,index+1)||
  42.                         solve(board, word, x, y-1, vis,index+1);
  43.         vis[x][y] = false;
  44.         return flag;
  45.     }