[没事儿刷两道-Leetcode面试题 13] 机器人的运动范围

题目

地上有一个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。请问该机器人能够到达多少个格子？题目来源

示例 1：
输入：m = 2, n = 3, k = 1
输出：3
示例 2：
输入：m = 3, n = 1, k = 0
输出：1
其中
1 <= n,m <= 100
0 <= k <= 20

题解

看到题目一开始直接想到双重循环判断满足条件的点即可到达但实际上满足调条件的点可能不连续，如下图。因此不能简单的遍历整个图。

解法一：

广度优先算法，一层一层遍历的同时加入限制条件即可。

数位和计算：

int sumXy(int n){
        int sum = 0;
        while(n){
            sum += (n % 10);
            n /= 10;
        }
        return sum;
    }

由于1<=n,m<=100，所以x,y坐标点不会超过两位数，可以直接将代码优化为
(x / 10 + x % 10 + y / 10 + y % 10) > k

移动过程

使用两个数组dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0}来模拟移动过程，又因为起点为（0,0），因此仅向右和向下移动即可遍历全图，因此此步优化为dx[2] = {0,1},dy[2] = {1,0}

代码：

class Solution {
public:
    int movingCount(int m, int n, int k) {
        if(!k) return 1;
        vector<vector<int>> t(m,vector<int>(n,0));
        queue<pair<int,int> > q;
        int x,y,l,ans = 1;
        int dx[2] = {1,0},dy[2] = {0,1};
        t[0][0] = 1;q.push(make_pair(0,0));
        while(!q.empty()){
            auto [nx,ny] = q.front();
            q.pop();
            for(l = 0;l < 2;l++){
                x = nx + dx[l];y = ny + dy[l];
                if(x < 0 || x >= m || y < 0 || y >= n || t[x][y] || (x / 10 + x % 10 + y / 10 + y % 10) > k> k){
                    continue;
                }
                q.push(make_pair(x,y));
                ans++;
                t[x][y] = 1;
            }
        }    
        return ans;
    }
};

解法二：

深度优先算法：分别向右和向下移动，走过的格子标为1避免重复走，每走一步加1，其中条件判断与广度算法相同。

代码

class Solution {
public:
    vector<vector<int>> t(100,0);
    int movingCount(int m, int n, int k) {
        return dfs(0, 0, m, n, k);
    }
    int dfs(int x, int y, int m, int n, int k) {
        if (t[x][y] == 1 || x < 0 || y < 0 || x >= m || y >= n || (x / 10 + x % 10 + y / 10 + y % 10) > k)
            return 0;
        t[x][y] = 1;
        return dfs(x + 1, y, m, n, k) + dfs(x, y + 1, m, n, k) + 1;
    }
};