79. Word Search

题目链接

https://leetcode.com/problems/word-search/

解题思路

dfs

代码

int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty()) {
            return true;
        }
        vector<vector<bool>> mark(board.size(), vector<bool>(board[0].size(), false));
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[i].size(); ++j) {
                if (dfs(board, mark, i, j, word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& board, vector<vector<bool>> &mark, int n, int m, string &word, int p) {
        if (board[n][m] == word[p]) {
            if (word.length() == p + 1) {
                return true;
            }
            
            mark[n][m] = true;
            for (int i = 0; i < 4; ++i) {
                int n1 = n + dir[i][0], m1 = m + dir[i][1];
                if (n1 < 0 || n1 >= board.size() || m1 < 0 || m1 >= board[0].size()) {
                    continue;
                }
                if (!mark[n1][m1] && dfs(board, mark, n1, m1, word, p + 1)) {
                    return true;
                }
            }
            mark[n][m] = false;
        }
        return false;
    }
};