[每日一道小算法（七十三）][DFS] 机器人的运动范围（剑指offer习题）

Myth丶恋晨 2023-07-08 02:53 17阅读 0赞

前言：  
这是剑指offer习题中的最后一道题。也算把剑指offer刷了一遍。总的来说收获很大。从明天开始刷leetcode的习题。同时每天复习几道剑指offer的习题。

### 题目描述 ###

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

### 解题思路 ###

一般这种题都可以用DFS来解决。也就是我们从\[0,0\]开始，每成功走一步标记当前位置为true,然后从当前位置往四个方向探索，返回1 + 4 个方向的探索值之和。  
在探索时，判断当前节点是否可达的标准为：  
1）当前节点在矩阵内；  
2）当前节点未被访问过；  
3）当前节点满足limit限制。

### 代码样例 ###

package com.asong.leetcode.RobotmovingCount;
    
    /** * 机器人的运动范围 */
    public class Solution1 { 
        private int[] dx = { 1,-1,0,0};
        private int[] dy = { 0,0,1,-1};
        public int movingCount(int threshold, int rows, int cols)
        { 
            if(threshold<0||rows<=0||cols<=0)
            { 
                return 0;
            }
            boolean[][] visited = new boolean[rows][cols];
            return 1+move(threshold,rows,cols,0,0,visited);
        }
        public int sum(int n)
        { 
            int ans = 0;
            while (n>0)
            { 
                ans +=n%10;
                n = n/10;
            }
            return ans;
        }
        public int move(int threshold,int rows,int cols,int x,int y,boolean[][] visited)
        { 
            visited[x][y] = true;
            int ans = 0;
            for (int i = 0; i < 4; i++) { 
                int X = x + dx[i];
                int Y = y + dy[i];
                if(X>=0&&Y>=0&&X<rows&&Y<cols&&!visited[X][Y]&&(sum(X)+sum(Y)<=threshold))
                { 
                    ans += move(threshold,rows,cols,X,Y,visited)+1;
                }
            }
            return ans;
        }
    
        public static void main(String[] args) { 
            Solution solution = new Solution();
            solution.movingCount(18,10,10);
        }
    }