单词搜索

给出一个二维的字母板和一个单词，寻找字母板网格中是否存在这个单词。

单词可以由按顺序的相邻单元的字母组成，其中相邻单元指的是水平或者垂直方向相邻。每个单元中的字母最多只能使用一次。

样例
给出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;
    }
};