题目描述

地上有一个 m 行和 n 列的方格，横纵坐标范围分别是 0∼m−1 和 0∼n−1。

一个机器人从坐标 (0,0) 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。

但是不能进入行坐标和列坐标的数位之和大于 k 的格子。

请问该机器人能够达到多少个格子？

样例

样例1
输入：k=7, m=4, n=5

输出：20
样例2
输入：k=18, m=40, n=40

输出：1484

解释：当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。
      但是，它不能进入方格（35,38），因为3+5+3+8 = 19。
注意:

0<=m<=50
0<=n<=50
0<=k<=100

算法1

(dfs) $O(n^2)$

C++ 代码

class Solution {
public:
    int movingCount(int m, int n, int k) {
        vector<vector<int>> matrx(m,vector<int>(n, 0));
        dfs(matrx, 0, 0, k);
        int res = 0;
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                res += matrx[i][j];
                // cout<<matrx[i][j]<<" ";
            }
            // cout<<endl;
        }
        return res;

    }
    void dfs(vector<vector<int>> &matrx, int i, int j, int k){   //只能从0，0开始走
        if(matrx[i][j] == 1) return;
        int sum = 0, ia = i, ja = j;
        while(ia){
            sum += ia % 10;
            ia = ia / 10;
        }
        while(ja){
            sum += ja % 10;
            ja = ja / 10;
        }
        if(sum > k) return;
        matrx[i][j] = 1;

        int dx[4] = {-1, 1, 0, 0};
        int dy[4] = {0, 0, -1, 1};
        for(int index = 0; index < 4; ++index){
            int x = i + dx[index];
            int y = j + dy[index];
            if(x >= 0 && x < matrx.size() && y >= 0 && y < matrx[0].size()){
                dfs(matrx, x, y, k);
            }
        }
    }
};

算法2

(bfs) $O(n^2)$

C++ 代码

class Solution {
public:
    int add1(int x){
        int res = 0;
        while(x){
            res += x % 10;
            x /= 10;
        }
        return res;
    }
    int add2(pair<int, int> x){
        int res = 0;
        res = add1(x.first) + add1(x.second);
        return res;
    }

    int movingCount(int threshold, int rows, int cols)
    {
        if(rows == 0 || cols == 0 ) return 0;

        vector<vector<bool>> steps(rows, vector<bool>(cols, false));
        queue<pair<int, int>> q;
        int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

        int res = 0;
        q.push({0,0});
        while(!q.empty()){
            auto tmp = q.front();
            int sum = add2(tmp);
            q.pop();

            // if(sum <= threshold){//这样判断不行，在扩展的时候，会扩展到同一个位置，也就是说同一个位置可能在队列中出现多次。
            if(sum <= threshold && !steps[tmp.first][tmp.second]){
                ++res;
                // cout<<tmp.first<<":"<<tmp.second<<endl;
                steps[tmp.first][tmp.second] = true;

                for(int i = 0; i < 4; ++i){
                    int x = tmp.first + dx[i], y = tmp.second + dy[i];
                    if(x >=0 && x < rows && y >=0 && y < cols && !steps[x][y]){
                        q.push({x, y});
                    }
                }
            }
        }
        return res;

    }
};