leetcode79. 单词搜索 网格地图搜索+回溯经典写法啦

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

思路：搜索回溯基本上是经典模板题了。

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     
 private boolean[][] marked;
     
    
   

    

     

    
    

     
 // x-1,y
     
    
   

    

     

    
    

     
 // x,y-1 x,y x,y+1
     
    
   

    

     

    
    

     
 // x+1,y
     
    
   

    

     

    
    

     
 private int[][] direction = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
     
    
   

    

     

    
    

     
 // 盘面上有多少行
     
    
   

    

     

    
    

     
 private int m;
     
    
   

    

     

    
    

     
 // 盘面上有多少列
     
    
   

    

     

    
    

     
 private int n;
     
    
   

    

     

    
    

     
 private String word;
     
    
   

    

     

    
    

     
 private char[][] board;
     
    
   

    

     

    
    

     
 public boolean exist(char[][] board, String word) {
     
    
   

    

     

    
    

     

       m = board.length;
     
    
   

    

     

    
    

     
 if (m == 0)return false;
     
    
   

    

     

    
    

     

       n = board[0].length;
     
    
   

    

     

    
    

     

       marked = new boolean[m][n];
     
    
   

    

     

    
    

     
 this.word = word;
     
    
   

    

     

    
    

     
 this.board = board;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 for (int i = 0; i < m; i++)
     
    
   

    

     

    
    

     
 for (int j = 0; j < n; j++)
     
    
   

    

     

    
    

     
 if (dfs(i, j, 0))
     
    
   

    

     

    
    

     
 return true;
     
    
   

    

     

    
    

     
 return false;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 private boolean dfs(int i, int j, int start) {
     
    
   

    

     

    
    

     
 if (start == word.length() - 1) {
     
    
   

    

     

    
    

     
 return board[i][j] == word.charAt(start);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if (board[i][j] == word.charAt(start)) {
     
    
   

    

     

    
    

     

       marked[i][j] = true;
     
    
   

    

     

    
    

     
 for (int k = 0; k < 4; k++) {
     
    
   

    

     

    
    

     
 int newX = i + direction[k][0];
     
    
   

    

     

    
    

     
 int newY = j + direction[k][1];
     
    
   

    

     

    
    

     
 if (newX >= 0 && newX < m && newY >= 0 && newY < n && !marked[newX][newY]) {
     
    
   

    

     

    
    

     
 if (dfs(newX, newY, start + 1)) {
     
    
   

    

     

    
    

     
 return true;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       marked[i][j] = false;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return false;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/104429737