[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 
// 
// Related Topics 数组 回溯算法 
// 👍 796 👎 0

/*
* 79 单词搜索
* 2021-02-28 11:18:06
* @author oxygenbytes
*/ 
#include "leetcode.h" 
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    int n, m;
    bool exist(vector<vector<char>>& board, string word) {

        m = board.size();
        n = board[0].size();

        if(word.empty()) return true;
        if(board.empty() || board[0].empty()) return false;

        for(int i = 0;i < m;i++){
            for(int j = 0; j < n;j++){
                if(board[i][j] == word[0]){
                    if(dfs(board,word, i, j, 0)) return true;
                }
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& board,string& word, int x, int y, int cur){
        if(board[x][y] != word[cur]) return false; // 比较最后一个字符后，再根据cur判断
        if(cur == word.size() - 1) return true;

        int dx[4] = {-1, 0, 1, 0};
        int dy[4] = {0, 1, 0, -1};

        board[x][y] = '.'; // 不回溯

        for(int i = 0;i < 4;i++){
            int a = x + dx[i];
            int b = y + dy[i];

            if(a >= 0 && a < m && b >= 0 && b < n){
                if(dfs(board, word, a, b, cur + 1)){
                    return true;
                }
            }
        }
        board[x][y] = word[cur];
        return false;
    }
};
//leetcode submit region end(Prohibit modification and deletion)