1
class Solution {
2
  public boolean exist(char[][] board, String word) {
3
    boolean vis[][] = new boolean[board.length][board[0].length];
4
    for (int i = 0; i < board.length; i++) {
5
      for (int j = 0; j < board[0].length; j++) {
6
        if (word.charAt(0) == board[i][j]) {
7
          boolean is = isexist(i, j, board, vis, 1, word);
8
          if (is) return true;
9
        }
10
      }
11
    }
12
    return false;
13
  }
14

15
  static int dir[][] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
16

17
  static boolean isexist(int r, int c, char board[][], boolean vis[][], int idx, String word) {
18
    if (idx == word.length()) return true;
19
    vis[r][c] = true;
20
    for (int k = 0; k < 4; k++) {
21
      int rd = r + dir[k][0];
22
      int cd = c + dir[k][1];
23
      if (rd < 0
24
          || cd < 0
25
          || rd >= board.length
26
          || cd >= board[0].length
27
          || vis[rd][cd] == true
28
          || board[rd][cd] != word.charAt(idx)) continue;
29
      boolean is = isexist(rd, cd, board, vis, idx + 1, word);
30
      if (is) return true;
31
    }
32
    vis[r][c] = false;
33
    return false;
34
  }
35
}