面试题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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof

思路：

这个思路没法写，因为真的有盲点，直接看链接的思路最好

https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/solution/mian-shi-ti-13-ji-qi-ren-de-yun-dong-fan-wei-dfs-b/

bfs的代码还未写，后面补上

代码1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//dfs
class Solution {
    boolean[][] isvisited;//访问数组
    int mm,nn,kk;
    public int movingCount(int m, int n, int k) {
        //先用上一题的深搜思想
        mm=m;
        nn=n;
        kk=k;
        isvisited = new boolean[m][n];
        return dfs(0,0,0,0);
    }
    public int dfs(int r,int c,int rr,int cc){
        //计算r+c,参数rr和cc
        if(r>=mm||c>=nn ||isvisited[r][c]||rr+cc>kk)//越界，越界，已访问，数值超过
            return 0;
        //置访问位为1
        isvisited[r][c]=true;
        //根据思路中，只能向下和向右，那么只需要这两个方向dfs即可
        return 1+dfs(r+1,c,(r+1)%10!=0?rr+1:rr-8,cc)+dfs(r,c+1,rr,(c+1)%10!=0?cc+1:cc-8);

    }
}