一、原題

　　Given a 2D board and a Word, find if the word exists in the grid. 　　The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. 　　For example, 　　Given board =

[  ["ABCE"],  ["SFCS"],  ["ADEE"]]1234512345
　　word = "ABCCED", -> returns true, 　　word = "SEE", -> returns true, 　　word = "ABCB", -> returns false. 
一、中文
　　給定一個board字符矩陣，可以從任意一個點開始經過上下左右的方式走，每個點只能走一次，如果存在一條路走過的字符等于給定的字符串，那么返回true 
三、舉例
見上面的英文描述
四、思路
　　這個題目還是有點難度的，自己想了半天只想了一個大概，最后還不得不參考了大神的方法了。這里關鍵點是要知道是層層遞歸的，他的每一個分支都有上下左右四個分支來進行遞歸，如果遞歸不成功就進行回溯。還有一個難點就是標記矩陣的作用域以及作用，其作用域是全局的，一開始不是很理解，認為每個點都有一個才對，其實他在回溯的過程中又變成了false，所以是沒有影響的，相當于每個點都有一個，其作用是保證在一條路徑上不重復對某個點進行遍歷。
五、程序
用回溯法進行搜索 
package code;public class LeetCode45{	public static void main(String args[]){		char num[][] = new char[][]{			{'A', 'B', 'C', 'E'},			{'S', 'F', 'C', 'S'},			{'A', 'D', 'E', 'E'}		};				boolean e1 = isExist(num, "ABCCED");		boolean e2 = isExist(num, "ABEE");				System.out.PRintln(e1+" "+e2);	}	//驗證單詞是否能搜索到	public static boolean isExist(char[][] num, String word){		//標記矩陣，用來表示該元素是否被訪問過，是否被訪問的過是表的是在一條對的路徑上沒有被訪問過，這樣可以保證不重復遍歷元素		boolean [][] visited = new boolean[num.length][num[0].length];				//每一個位置為起點進行搜索        for (int i = 0; i < num.length; i++) {            for (int j = 0; j < num[0].length; j++) {                if (search(num, visited, i, j, word, new int[]{0})) {                    return true;                }            }        }                return false;	}		/**	 * @param num	 * @param visited	 * @param row  訪問的元素的行號	 * @param col  訪問的元素的列號	 * @param word 匹配的字符串	 * @param idx  匹配的位置	 * @return	 */	private static boolean search(char[][] num, boolean[][] visited, int row, int col, String word, int[] index) {		if(index[0] == word.length()){			return true;		}				//從該點開始是否有其他路徑		boolean haspath = false;				//判斷當前位置是否合法，并且該元素是否和字符串中的元素相匹配		if(check(num, visited, row, col, word, index[0])){			//標記被訪問過了			visited[row][col] = true;						//移動到單詞的下一個元素			index[0]++;						//對上下左右的四個方向進行搜索，也就是上下左右只要有一個方向和目標字符串的下一個單詞想匹配，就OK            hasPath = search(num, visited, row - 1, col, word, index ) // 上                    || search(num, visited, row, col + 1, word, index) // 右                    || search(num, visited, row + 1, col, word, index) // 下                    || search(num, visited, row, col - 1, word, index); // 左                        //如果沒有找到路徑，就標記該點不行了,進行回溯            if(!hasPath){            	visited[row][col] = false;            	index[0]--;            }		}				return hasPath;	}	    /**     * @param num     * @param visited     * @param row     * @param col     * @param word     * @param index     * @return     */    public static boolean check(char[][] num, boolean[][] visited, int row, int col, String word, int index) {        return  row >= 0 && row < num.length 			// 行號合法                && col >= 0 && col < num[0].length	    // 列號合法                && !visited[row][col] 					// 沒有被訪問過                && num[row][col] == word.charAt(index); // 字符相等    }}	-----------------------------------------output----------------------------------------------
true false