C++刷LeetCode（79. 单词搜索）【回溯】

糖逗

题目描述：

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

 

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false
 

提示：

board 和 word 中只包含大写和小写英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3

class Solution {
public:
    bool dfs(vector<vector<char>>& board, string& word, int i, int j, int len){
        if(i < 0 || j < 0 || i >= board.size() || j >= board[0].size() || board[i][j] == '1' || board[i][j] != word[len] || len >= word.size()){
            if(len == word.size())return true;
            else return false;
        }
        char temp = board[i][j];
        board[i][j] = '1';
        bool res = dfs(board, word, i + 1, j, len + 1) || dfs(board, word, i - 1, j, len + 1) || dfs(board, word, i, j - 1, len + 1) || dfs(board, word, i, j + 1, len + 1);
        board[i][j] = temp;
        return res;
    }
    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(board[i][j] == word[0]){
                    if(dfs(board, word, i, j, 0))return true;
                }
            }
        }
        return false;
    }
};