給定一個二維網格和一個單詞，找出該單詞是否存在于網格中。

單詞必須按照字母順序，通過相鄰的單元格內的字母構成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母不允許被重復使用。

示例:

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,yprivate 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;}
}

?