地上有一个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
  • 👍 302
  • 👎 0

    • 题解

    依旧广搜实现，从右上角开始，移动方向必然只能向右或者向下，再排除掉重复的部分

    
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int movingCount(int m, int n, int k) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0,0});
        boolean[][] checked = new boolean[m][n];
        checked[0][0] = true;
        int count = 1;
        while (!queue.isEmpty()){
            int[] current = queue.poll();
            int[] nextToX = getToX(current);
            if (nextToX[0] < m && nextToX[1] < n && !checked[nextToX[0]][nextToX[1]] && isReachedAble(nextToX,k)){
                checked[nextToX[0]][nextToX[1]]= true;
                queue.offer(nextToX);
                count++;
            }

            int[] nextToY = getToY(current);
            if (nextToY[0] < m && nextToY[1] < n && !checked[nextToY[0]][nextToY[1]] && isReachedAble(nextToY,k)){
                checked[nextToY[0]][nextToY[1]]= true;
                count++;
                queue.offer(nextToY);
            }

        }
        return count;
    }

    private boolean isReachedAble(int[] position, int k){
        int sum = getSum(position[0]) + getSum(position[1]);
        return sum <=k;
    }

    private int getSum(int num){
        int sum = 0;
        while (num > 9){
            sum += num % 10;
            num /= 10;
        }
        return sum + num;
    }

    private int[] getToX(int[] position){
        return new int[]{position[0]+1,position[1]};
    }
    private int[] getToY(int[] position){
        return new int[]{position[0],position[1]+1};
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    从矩阵的最终表现上来说，这题中小机器人的可行走范围是有规律的

    思路：判断vis[i][j]是否可达，如果可达返回1，反之返回0；判断i+j是否⼤于k，如果⼤于k，vis[i][j]则不可达。
    我们只需要向下和向右搜索，因此我们到达（i，j）的路线只能从（i-1，j）或（i，j-1）⾛过(不考虑边界)。那么我
    们就得出了这样⼀个公式：

    vis[i][j] = vis[i − 1][j] OR vis[i][j − 1]

    只要有⼀个格⼦可以到达那么（i，j）就能到达。因此我们只需要遍历所有格⼦然后去计算他们是否可达，同时记
    录可达的格⼦数量即可。

    放个代码实现如下

    class Solution {
    public int movingCount(int m, int n, int k) {
        if (k == 0) return 1;
        boolean[][] vis = new boolean[m][n];
        int ans = 1;
        vis[0][0] = true;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0 || get(i) + get(j) > k) continue;
                if (i - 1 >= 0) vis[i][j] |= vis[i - 1][j];
                if (j - 1 >= 0) vis[i][j] |= vis[i][j - 1];
                ans += vis[i][j] ? 1 : 0;
            }
        }
        return ans;
    }
    public int get(int x) {
        int res = 0;
        while (x != 0) {
            res += x % 10;
            x /= 10;
        }
        return res;
    }
}