```
public class Solution {
private boolean dfs(char[][] board, char[] w, int start, int i, int j, boolean[][] visited, int m, int n) {
if (visited[i][j]) return false;
if (board[i][j] != w[start]) return false;
if (start == w.length-1) return true;
visited[i][j] = true;
if (i+1 < m) {if (dfs(board, w, start+1, i+1, j, visited, m, n)) return true;}
if (i-1 >= 0) {if (dfs(board, w, start+1, i-1, j, visited, m, n)) return true;}
if (j-1 >= 0) {if (dfs(board, w, start+1, i, j-1, visited, m, n)) return true;}
if (j+1 < n) {if (dfs(board, w, start+1, i, j+1, visited, m, n)) return true;}
visited[i][j] = false;
return false;
}
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) return false;
if (word == null) return false;
int m = board.length, n = board[0].length;
boolean[][] visited = new boolean[m][n];
char[] w = word.toCharArray();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] != w[0]) continue;
if (dfs(board, w, 0, i, j, visited, m, n)) return true;
}
}
return false;
}
```

}