美文网首页
机器人的运动范围

机器人的运动范围

作者: 神游物外的轮子 | 来源:发表于2019-08-11 16:52 被阅读0次

    记忆点

    • 递归
    • (0, 0)开始

    思路

    用递归。
    目标是从(0, 0)开始,找到所有的可以访问的点,所以理论上矩阵上的每个点最多访问一次。

    实现

    class Solution {
    public:
        int getSum (int x, int y) {
            int s = 0;
            while (x) {
                s += x % 10;
                x /= 10;
            }
            while (y) {
                s += y % 10;
                y /= 10;
            }
            return s;
        }
    
        int step(int x, int y, int threshold, vector<vector<bool>>& visited) {
            if (x < 0 || x >= visited.size() || y < 0 || y >= visited[x].size()) return 0;
            if (visited[x][y] || getSum(x, y) > threshold) return 0;
    
            int cnt = 1;
            visited[x][y] = true;
            cnt += step(x+1, y, threshold, visited);
            cnt += step(x-1, y, threshold, visited);
            cnt += step(x, y+1, threshold, visited);
            cnt += step(x, y-1, threshold, visited);
            return cnt;
        }
    
        int movingCount(int threshold, int rows, int cols) {
            if (threshold < 0 || rows <= 0 || cols <= 0) return 0;
    
            int cnt = 0;
            vector<vector<bool>> visited(rows, vector<bool>(cols, false));
            cnt += step(0, 0, threshold, visited);
            return cnt;
        }
    };
    

    相关文章

      网友评论

          本文标题:机器人的运动范围

          本文链接:https://www.haomeiwen.com/subject/wcssjctx.html