1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| class Solution { static private int[][] dirt = new int[][]{{1, 0},{-1, 0},{0, 1},{0, -1}}; public boolean exist(char[][] board, String word) { if (board == null || board.length == 0 || board[0].length == 0) return false; if (word == null || word.length() == 0) return true; char[] w = word.toCharArray(); boolean[][] visited = new boolean[board.length][board[0].length]; for (int i = 0; i < board.length; i++) for (int j = 0; j < board[0].length; j++) if (dfs(board, i, j, w, 0, visited)) return true; return false; } public boolean dfs(char[][] board, int x, int y, char[] w, int cur, boolean[][] visited){ if (board[x][y] != w[cur]) return false; if (cur == w.length - 1) return true; visited[x][y] = true; for (int i = 0; i < 4; i++){ int nx = x + dirt[i][0]; int ny = y + dirt[i][1]; if (nx >= 0 && nx < board.length && ny >=0 && ny < board[0].length && !visited[nx][ny]){ if (dfs(board, nx, ny, w, cur + 1, visited)) return true; } } visited[x][y] = false; return false; } }
|