###### tags: `LeetCode` `Recursion` `DFS` `String` `Medium`
# LeetCode #79 [Word Search](https://leetcode.com/problems/word-search/)
### (Medium)

給定一個 m x n 二維字符網格 board 和一個字符串單詞 word 。如果 word 存在於網格中，返回 true ；否則，返回 false 。

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

---

先在整個二維數組中尋找符合第一個字母的位置, 並在該處開始進行遞迴呼叫。

每當找到符合的字母時, 只需遞迴呼叫該位置的上下左右位置即可; 而當負責標示現在尋找的字母的指針大小等於給定字串長度時, 代表完成搜索, 此時回傳true。

此外, 在遞迴呼叫前將現在點的字元設為#, 並在呼叫後還原成原本的內容, 以避免重複探索。

注意邊界條件避免溢位。

---

//208ms, faster than 82.78%

class Solution {
public:
    bool exist(vector<vector<char>>& board, string& word) {
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[0].size();j++){
                if(dfs(board, word, i, j, 0))return true;
            }
        }
        return false;
    }
    bool dfs(vector<vector<char>>& board, string& word, int i, int j, int pos){
        if(i<0||j<0||i==board.size()||j==board[0].size()||board[i][j]!=word[pos])return false;
        if(pos==word.size()-1)return true; 
        if(board[i][j]==word[pos]){
            char c=board[i][j];
            board[i][j]='#';
            if(dfs(board, word, i-1, j, pos+1))return true;
            else if(dfs(board, word, i, j+1, pos+1))return true;
            else if(dfs(board, word, i+1, j, pos+1))return true;
            else if(dfs(board, word, i, j-1, pos+1))return true;
            board[i][j]=c;
        }  
        return false;
    }
};