給出一個(gè)二維的字母板和一個(gè)單詞赎离，尋找字母板網(wǎng)格中是否存在這個(gè)單詞辅鲸。

單詞可以由按順序的相鄰單元的字母組成孩擂，其中相鄰單元指的是水平或者垂直方向相鄰凸郑。每個(gè)單元中的字母最多只能使用一次谨湘。

樣例
給出board =

[

  "ABCE",

  "SFCS",

  "ADEE"

]

word = "ABCCED"搞莺， ->返回 true,

word = "SEE"蝙昙，-> 返回 true,

word = "ABCB"轻局， -> 返回 false.

class Solution {
public:
    /**
     * @param board: A list of lists of character
     * @param word: A string
     * @return: A boolean
     */
    bool exist(vector<vector<char> > &board, string word) {
        // write your code here
        int boardH = board.size();
        if (boardH == 0) {
            return false;
        }
        
        int boardW = board[0].size();
        if (boardW == 0) {
            return false;
        }
        
        int wordWidth = word.size();
        
        vector<vector<bool> > visited(boardH,vector<bool>(boardW,false));
        
        for (int i = 0;i < boardH;i++) {
            for (int j = 0;j < boardW;j++) {
                if (board[i][j] == word[0]) {
                    if(dfs(board,visited,i,j,boardH,boardW,word,0,wordWidth)) {
                        return true;
                    }
                }
            }
        }
        
        return false;
    }
    
    bool dfs(vector<vector<char> > &board,vector<vector<bool> > &visited,int i,int j,int boardH,int boardW,string &word,int wordIndex,int wordWith) {
        
        
        
        if (j >= 0 && i >= 0 && i < boardH && j < boardW && visited[i][j] == false && wordIndex < wordWith && board[i][j] == word[wordIndex]) {
            
            
            if (wordIndex == wordWith-1) {
                return true;
            }
            visited[i][j] = true;
            if(dfs(board,visited,i-1,j,boardH,boardW,word,wordIndex+1,wordWith)) {
                return true;
            }
            
            if(dfs(board,visited,i+1,j,boardH,boardW,word,wordIndex+1,wordWith)) {
                return true;
            }
            
            if(dfs(board,visited,i,j-1,boardH,boardW,word,wordIndex+1,wordWith)) {
                return true;
            }
            
            if(dfs(board,visited,i,j+1,boardH,boardW,word,wordIndex+1,wordWith)) {
                return true;
            }
            visited[i][j] = false;
        }
        
        return false;
    }
};