Leetcode题解剑指 Offer 13. 机器人的运动范围

PROBLEM

难度中等

MY ANSWER

使用DFS解决，矩阵visit表示移动中是否走过该格子。DFS完成后，遍历visit得出到达的格子数。时间复杂度O(mn)，空间复杂度O(mn)。

class Solution {
public:
    int k, r, c;
    vector<vector<int>> visit;
    int sum(int m, int n) {
        int s = 0;
        while(m) {
            s += m % 10;
            m /= 10;
        }
        while(n) {
            s += n % 10;
            n /= 10;
        }
        return s;
    }
    void dfs(int m, int n) {
        if(sum(m, n) > k) {
            return;
        }
        else {
            visit[m][n] = 1;
            if(m + 1 < r &&  !visit[m + 1][n]) {
                dfs(m + 1, n);
            }
            if(n + 1 < c &&  !visit[m][n + 1]) {
                dfs(m, n + 1);
            }
            if(m - 1 > 0 &&  !visit[m - 1][n]) {
                dfs(m - 1, n);
            }
            if(n - 1 > 0 &&  !visit[m][n - 1]) {
                dfs(m, n - 1);
            }
        }
        return;
    }
    int movingCount(int m, int n, int k) {
        this->k = k;
        r = m;
        c = n;
        visit.resize(m);
        for(int i = 0; i < m; i++) {
            visit[i].resize(n);
        }
        dfs(0, 0);
        int count = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(visit[i][j]) {
                    count++;
                }
            }
        }
        return count;
    }
};

BETTER SOLUTION

DFS

递归中返回加一计算count。时间复杂度O(mn)，空间复杂度O(mn)。

class Solution {
public:
    int movingCount(int m, int n, int k) {
        vector<vector<bool>> visited(m, vector<bool>(n, 0));
        return dfs(0, 0, 0, 0, visited, m, n, k);
    }
private:
    int dfs(int i, int j, int si, int sj, vector<vector<bool>> &visited, int m, int n, int k) {
        if(i >= m || j >= n || k < si + sj || visited[i][j]) return 0;
        visited[i][j] = true;
        return 1 + dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj, visited, m, n, k) +
                   dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8, visited, m, n, k);
    }
};

BFS

初始化：将机器人初始点 (0, 0)(0,0) 加入队列 queue ；
迭代终止条件： queue 为空。代表已遍历完所有可达解。
迭代工作：
- 单元格出队：将队首单元格的索引、数位和弹出，作为当前搜索单元格。
- 判断是否跳过：若 ① 行列索引越界或 ② 数位和超出目标值 k 或 ③ 当前元素已访问过时，执行 continue 。
- 标记当前单元格：将单元格索引 (i, j) 存入 Set visited 中，代表此单元格已被访问过。
- 单元格入队：将当前元素的下方、右方单元格的索引、数位和加入 queue 。

时间复杂度O(mn)，空间复杂度O(mn)。

class Solution {
public:
    int movingCount(int m, int n, int k) {
        vector<vector<bool>> visited(m, vector<bool>(n, 0));
        int res = 0;
        queue<vector<int>> que;
        que.push({ 0, 0, 0, 0 });
        while(que.size() > 0) {
            vector<int> x = que.front();
            que.pop();
            int i = x[0], j = x[1], si = x[2], sj = x[3];
            if(i >= m || j >= n || k < si + sj || visited[i][j]) continue;
            visited[i][j] = true;
            res++;
            que.push({ i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj });
            que.push({ i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8 });
        }
        return res;
    }
};

递推

根据递推公式遍历所有格子：

任何数与0相或是本身，任何数与0异或是本身，自己与自己异或为0。

class Solution {
    int get(int x) {
        int res=0;
        for (; x; x /= 10){
            res += x % 10;
        }
        return res;
    }
public:
    int movingCount(int m, int n, int k) {
        if (!k) return 1;
        vector<vector<int> > vis(m, vector<int>(n, 0));
        int ans = 1;
        vis[0][0] = 1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if ((i == 0 && j == 0) || get(i) + get(j) > k) continue;
                // 边界判断
                if (i - 1 >= 0) vis[i][j] |= vis[i - 1][j];
                if (j - 1 >= 0) vis[i][j] |= vis[i][j - 1];
                ans += vis[i][j];
            }
        }
        return ans;
    }
};

SUMMARY

DFS使用递归实现，BFS使用队列实现；注意如何在递归中使用返回值进行count的计算。
使用queue实现队列。