13.机器人的运动范围 (Medium)*

题目描述*

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例*

输入：m = 2, n = 3, k = 1

输出：3

输入：m = 3, n = 1, k = 0

输出：1

提示*

1 <= n,m <= 100, 0 <= k <= 20

代码*

开始以为每行从左到右扫描就行了，但是提交了并不对，又想了一下，感觉自己实在是太蠢了，可走到的格子并不是每行连续的，只要本身值满足且左或上的满足就可以。本来还想用暴力统计的，但是脑子实在 8 行，细节总有问题，还是直接 dfs，只需要探索下和右就行了。还可以用 bfs，出队时判断下和右是否满足，满足则入队。

dfsbfs

class Solution {
private:
    int m, n, k;
public:
    int movingCount(int m, int n, int k) {
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        this->m = m, this->n = n, this->k = k;
        return dfs(visited, 0, 0);
    }

    // dfs
    int dfs(vector<vector<bool>>& visited, int i, int j) {
        if(i < 0 || i >= m || j < 0 || j >= n || visited[i][j] 
            || ((i%10 + i/10 + j%10 + j/10) > k)) {
            return 0;
        }
        visited[i][j] = true;
        return dfs(visited, i + 1, j) + dfs(visited, i, j + 1) + 1;
    }
};

class Solution {
private:
    int m, n, k;
public:
    int movingCount(int m, int n, int k) {
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        this->m = m, this->n = n, this->k = k;
        return bfs(visited);
    }

    // bfs
    int bfs(vector<vector<bool>>& visited) {
        queue<pair<int, int>> res;
        int cnt = 0;
        res.push({0, 0});
        visited[0][0] = true;
        while(!res.empty()) {
            int i = res.front().first, j = res.front().second;
            res.pop();
            cnt++;
            if((i + 1) < m && j < n && !visited[i + 1][j] && 
                ((i + 1)%10 + (i + 1)/10 + j/10 + j%10) <= k) {
                res.push({i + 1, j});
                visited[i + 1][j] = true;
            }
            if(i < m && (j + 1) < n && !visited[i][j + 1] && 
                ((j + 1)%10 + (j + 1)/10 + i/10 + i%10) <= k) {
                res.push({i, j + 1});
                visited[i][j + 1] = true;
            }
        }
        return cnt;
    }
};

最后更新: July 23, 2022