Robot range of motion (DFS)

---

title: The range of motion of the robot （DFS）
categories: LeetCode
tags:

• DFS
• Make a little progress every day

---

subject

The range of motion of the robot

difficulty secondary

There is one on the ground m That's ok n Grid of columns , From coordinates [0,0] To coordinates [m-1,n-1] . A robot from coordinates [0, 0] The grid starts to move , It can go left every time 、 Right 、 On 、 Move down one space （ Can't move out of the box ）, The sum of the digits of row coordinates and column coordinates is greater than k Lattice of . for example , When k by 18 when , Robots can enter the grid [35, 37] , because 3+5+3+7=18. But it can't get into the grid [35, 38], because 3+5+3+8=19. How many squares can the robot reach ？

Example 1：

Input ：m = 2, n = 3, k = 1
Output ：3

Example 2：

Input ：m = 3, n = 1, k = 0
Output ：1

Tips ：

1 <= n,m <= 100
0 <= k <= 20

Code ：

Java：

class Solution {    // result     int sum =0;    public int movingCount(int m, int n, int k) {        // Initializes a two-dimensional array to indicate whether it has accessed         boolean[][] visited = new boolean[m][n];        dfs(0,0,m,n,k,visited);        return sum;    }    private void dfs(int i,int j,int m,int n,int k,boolean[][] visited){        // Judge whether the conditions are met         if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || getSum(i)+getSum(j) > k){            return;        }        // Mark visited         visited[i][j] = true;        // Result plus 1        sum++;        // Depth-first search   Four directions         dfs(i-1,j,m,n,k,visited);        dfs(i+1,j,m,n,k,visited);        dfs(i,j-1,m,n,k,visited);        dfs(i,j+1,m,n,k,visited);    }    // Calculate digit sum     private int getSum(int num){        int sum =0;        while(num>0){            sum+=num%10;            num/=10;        }        return sum;    }}

C++：

class Solution {public:    int res = 0;public:    int movingCount(int m, int n, int k) {        vector<vector<bool>> visited(m, vector<bool>(n, 0));        dfs(0, 0, m, n, k, visited);        return res;    }public:    void dfs(int i, int j, int m, int n, int k, vector<vector<bool>> &visited) {        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || getSum(i) + getSum(j) > k) {            return;        }        visited[i][j] = true;        res++;        dfs(i + 1, j, m, n, k, visited);        dfs(i - 1, j, m, n, k, visited);        dfs(i, j + 1, m, n, k, visited);        dfs(i, j - 1, m, n, k, visited);    }public:    int getSum(int n) {        int sum = 0;        while (n) {            sum += n % 10;            n /= 10;        }        return sum;    }};

The above is the range of motion of the robot （DFS） The whole content of

Copyright notice ：
Original Blogger ： Cowherd Conan
Personal blog links ：https://www.keafmd.top/

If it helps you , Thank you for clicking on == One key, three links == Support ！
[ ha-ha ][ Huai Quan ]

come on. ！

Joint efforts ！

Keafmd

You can see it here , You know the following , Let's make progress together ！