剑指offer-回溯

1.矩阵中的路径

class Solution {
    int dx[4] = {0, -1, 0, 1}, dy[4] = {1, 0, -1, 0};
    bool dfs(vector<vector<char>>& matrix, int x, int y, string& word, int idx) {
        if (matrix[x][y] != word[idx]) return false;
        if (idx == word.size() - 1) return true;
        char ch = matrix[x][y];
        matrix[x][y] = '*';
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 and nx < matrix.size() and ny >= 0 and ny < matrix[0].size()) {
                if (dfs(matrix, nx, ny, word, idx + 1)) {
                    return true;
                }
            }
        }
        matrix[x][y] = ch;
        return false;
    }
public:
    bool hasPath(vector<vector<char> >& matrix, string word) {
        int m = matrix.size();
        if (m == 0) return false;
        int n = matrix[0].size();
        vector<vector<int>> st(m, vector<int>(n, false));
        for (int i = 0; i < m; ++i) {
            for (int j = 0;j < n; ++j) {
                if (dfs(matrix, i, j, word, 0))
                    return true;
            }
        }
        return false;
    }
};

2.机器人的运动范围

class Solution {
    int pointToSum(int x, int y) {
        int res = 0;
        while (x) { res += x % 10; x /= 10;}
        while (y) { res += y % 10; y /= 10;}
        return res;
    }
public:
    int movingCount(int threshold, int rows, int cols) {
        if (!rows or !cols) return 0;
        int res = 0;
        vector<vector<bool>> st(rows, vector<bool>(cols, false));
        int dx[4] = {0, -1, 0, 1}, dy[4] = {1, 0, -1, 0};
        
        queue<pair<int, int>> q;
        q.push({0, 0});
        while (q.size()) {
            auto [x, y] = q.front(); q.pop();
            if (pointToSum(x, y) > threshold or st[x][y]) continue;
            res++;
            st[x][y] = true;
            for (int i = 0; i < 4; ++i) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx >= 0 and nx < rows and ny >= 0 and ny < cols) {
                    q.emplace(nx, ny);
                }
            }
        }
        return res;
    }
};