给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E'] ]给定 word = "ABCCED", 返回 true. 给定 word = "SEE", 返回 true. 给定 word = "ABCB", 返回 false.
思路：类似于图的广搜，判断周围有没有给定word的下一个字母，如果有就继续下去，没有就回溯到之前位置，注意每添加一个字符，要把对应的那个位置给抹掉，因为不能重复使用一个位置的字符，回溯的时候又得让他出现。具体看代码：
public class 单词搜索 {public static void main(String[] args) {char[][] a = new char[][] {{'A','B','C','E'},{'S','F','E','S'},{'A','D','E','E'}};String word = "ABCESEEEFS";System.out.println(exist(a, word));}public static boolean exist(char[][] board, String word) {String str = "";for (int i = 0; i < board.length; i++) {for (int j = 0; j < board[0].length; j++) {if (board[i][j] == word.charAt(0)) {char[][] boardcopy = new char[board.length][board[0].length];arraycopy(board,boardcopy);if (digui(boardcopy,word,0,i,j,str)) {return true;}}}}return false;}private static void arraycopy(char[][] board, char[][] boardcopy) {for (int i = 0; i < board.length; i++) {for (int j = 0; j < board[i].length; j++) {boardcopy[i][j] = board[i][j];}}}private static boolean digui(char[][] board, String word, int n, int x, int y, String str) {if (str.equals(word)) {return true;}char[][] boardcopy = new char[board.length][board[0].length];arraycopy(board, boardcopy);//越界if (x<0 || x > board.length-1 || y < 0 || y > board[0].length - 1) {return false;}if (boardcopy[x][y] != word.charAt(n)) {return false;}else {str += boardcopy[x][y];boardcopy[x][y] = '.';}if (digui(boardcopy, word, n+1, x-1, y, str) ||digui(boardcopy, word, n+1, x+1, y, str) ||digui(boardcopy, word, n+1, x, y-1, str) ||digui(boardcopy, word, n+1, x, y+1, str)) {return true;}return false;}
}
