剑指 Offer 13 机器人的运动范围

    
        标签：
        
            剑指 Offer
        
    发布于：2022-01-22 12:13:56
    编辑于：2022-01-22 12:50:31
    浏览量：807

概述

https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

深度优先搜索 / 递归法

每个格子最多访问一次，因此时间复杂度 O(mn)。

class Solution {
public:
    int movingCount(int m, int n, int k) {
        vector<vector<bool>> flags(m, vector<bool>(n, false));
        return dfs(flags, m, n, k, 0, 0);
    }

    int dfs(vector<vector<bool>>& flags, int m, int n, int k, int i, int j) {
        if (i < 0 || j < 0 || i >= m || j >= n || flags[i][j] || !okay(i, j, k)) return 0;
        flags[i][j] = true;
        int count = 1 + dfs(flags, m, n, k, i + 1, j) + dfs(flags, m, n, k, i, j + 1) 
                      + dfs(flags, m, n, k, i - 1, j) + dfs(flags, m, n, k, i, j - 1);
        return count;
    }

    bool okay(int i, int j, int k) {
        return (i / 10 + j / 10 + i % 10 + j % 10) <= k;
    }
};

迭代法

考虑到开始位置为左上角，且 bot 必须从已可到达的位置前往下一个位置，即不能跳跃，因此判断一个格子可不可达只需要判断其上边和左边的是否可达，所以我们可以按照从上到下，从左到右的顺序遍历整个棋盘即可。

class Solution {
public:
    int movingCount(int m, int n, int k) {
        vector<vector<bool>> flags(m, vector<bool>(n, false));
        int count = 0;
        for (int i=0; i < m; i++) {
            for (int j=0; j < n; j++) {
                if (!okay(i, j, k)) continue;
                if (i == 0 && j == 0) flags[i][j] = true;
                if (i > 0 && flags[i-1][j]) flags[i][j] = true;
                if (j > 0 && flags[i][j-1]) flags[i][j] = true;
                if (flags[i][j] == true) {
                    count += 1;
                }
            }
        }
        return count;
    }

    bool okay(int i, int j, int k) {
        return (i / 10 + j / 10 + i % 10 + j % 10) <= k;
    }
};

迭代法（早停优化）

行首不行的话，该行其余元素也必然不行，这又将导致剩余行也必然不行。

但要注意，对于非行首元素，不能因为其不行就断言其之后的也不行，因为它之后的元素的数位和未必比它大，例如 19 和 23。

class Solution {
public:
    int movingCount(int m, int n, int k) {
        vector<vector<bool>> flags(m, vector<bool>(n, false));
        int count = 0;
        for (int i=0; i < m; i++) {
            if (!okay(i, 0, k)) break;  # 这里！
            for (int j=0; j < n; j++) {
                if (!okay(i, j, k)) continue;
                if (i == 0 && j == 0) flags[i][j] = true;
                if (i > 0 && flags[i-1][j]) flags[i][j] = true;
                if (j > 0 && flags[i][j-1]) flags[i][j] = true;
                if (flags[i][j] == true) {
                    count += 1;
                }
            }
        }
        return count;
    }

    bool okay(int i, int j, int k) {
        return (i / 10 + j / 10 + i % 10 + j % 10) <= k;
    }
};

广度优先搜索

维护一个队列，其中记录当前可以探索的点，探索该点后将新的可探索点加入队列，同时踢出该点。

Links: sword-offer-13