当前位置：网站首页>[daily algorithm 94] classic interview question: motion range of robot

[daily algorithm 94] classic interview question: motion range of robot

2022-07-27 09:00:00 【51CTO】

I've been busy interviewing recently , I didn't want to change today , But I'm too tired to read the basic knowledge , So I wrote a question to solve the pressure .

Topic link

LeetCode Interview questions 13. The range of motion of the robot [1]

Title Description

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
      
1.
2.
3.
4.

Example 2

       
        Input ：
       
m = 3, n = 1, k = 0
       
 Output ：
       
1
      
1.
2.
3.
4.

explain ：

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

Answer key

There is no algorithm for this problem , Relatively simple , Mainly examine your code implementation ability , Here I write two methods , One BFS, One DFS.

BFS

BFS The idea is to use a queue to save the nodes to be accessed , And keep getting out of the team , Join the nodes around the current node that meet the requirements . In order to avoid repeated visits , You can use a vis Array to mark the node location that has been accessed .

DFS

DFS The idea is clearer and simpler , For a node , The total number of nodes that can be accessed from it is equal to the total number of nodes that can be accessed from the nodes around it plus one . You also need to use one vis Array to mark the node location that has been accessed .

Code

BFS（c++）

       
       class 
       
       Solution {
       
       public:
       
       int 
       
       countDigit(
       
       int 
       
       x, 
       
       int 
       
       y) {
       
       int 
       
       sum 
       
       = 
       
       0;
       
       while (
       
       x 
       
       > 
       
       0) {
       
       sum 
       
       += 
       
       x 
       
       % 
       
       10;
       
       x 
       
       /= 
       
       10;
       
        }
       
       while (
       
       y 
       
       > 
       
       0) {
       
       sum 
       
       += 
       
       y 
       
       % 
       
       10;
       
       y 
       
       /= 
       
       10;
       
        }
       
       return 
       
       sum;
       
    }
       
       int 
       
       movingCount(
       
       int 
       
       m, 
       
       int 
       
       n, 
       
       int 
       
       k) {
       
       int 
       
       dx[
       
       4] 
       
       = {
       
       0, 
       
       0, 
       
       1, 
       
       -
       
       1};
       
       int 
       
       dy[
       
       4] 
       
       = {
       
       1, 
       
       -
       
       1, 
       
       0, 
       
       0};
       
       int 
       
       res 
       
       = 
       
       0;
       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       > 
       
       > 
       
       vis(
       
       m, 
       
       vector
       
       <
       
       int
       
       >(
       
       n, 
       
       0));
       
       queue
       
       <
       
       pair
       
       <
       
       int, 
       
       int
       
       > 
       
       > 
       
       Q;
       
       Q.
       
       push({
       
       0, 
       
       0});
       
       vis[
       
       0][
       
       0] 
       
       = 
       
       1;
       
       while (
       
       !
       
       Q.
       
       empty()) {
       
       pair
       
       <
       
       int, 
       
       int
       
       > 
       
       p 
       
       = 
       
       Q.
       
       front();
       
       Q.
       
       pop();
       
       res
       
       ++;
       
       int 
       
       nx 
       
       = 
       
       p.
       
       first, 
       
       ny 
       
       = 
       
       p.
       
       second;
       
       for (
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       4; 
       
       ++
       
       i) {
       
       int 
       
       x 
       
       = 
       
       nx 
       
       + 
       
       dx[
       
       i], 
       
       y 
       
       = 
       
       ny 
       
       + 
       
       dy[
       
       i];
       
       if (
       
       0 
       
       <= 
       
       x 
       
       && 
       
       x 
       
       < 
       
       m 
       
       && 
       
       0 
       
       <= 
       
       y 
       
       && 
       
       y 
       
       < 
       
       n 
       
       && 
       
       !
       
       vis[
       
       x][
       
       y] 
       
       && 
       
       countDigit(
       
       x, 
       
       y) 
       
       <= 
       
       k) {
       
       vis[
       
       x][
       
       y] 
       
       = 
       
       1;
       
       Q.
       
       push({
       
       x, 
       
       y});
       
                }
       
            }
       
        }
       
       return 
       
       res;
       
    }
       
};
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.

DFS（c++）

       
       class 
       
       Solution {
       
       public:
       
       int 
       
       dx[
       
       4] 
       
       = {
       
       0, 
       
       0, 
       
       1, 
       
       -
       
       1};
       
       int 
       
       dy[
       
       4] 
       
       = {
       
       1, 
       
       -
       
       1, 
       
       0, 
       
       0};
       
       int 
       
       countDigit(
       
       int 
       
       x, 
       
       int 
       
       y) {
       
       int 
       
       sum 
       
       = 
       
       0;
       
       while (
       
       x 
       
       > 
       
       0) {
       
       sum 
       
       += 
       
       x 
       
       % 
       
       10;
       
       x 
       
       /= 
       
       10;
       
        }
       
       while (
       
       y 
       
       > 
       
       0) {
       
       sum 
       
       += 
       
       y 
       
       % 
       
       10;
       
       y 
       
       /= 
       
       10;
       
        }
       
       return 
       
       sum;
       
    }
       
       int 
       
       dfs(
       
       int 
       
       nx, 
       
       int 
       
       ny, 
       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       > 
       
       >& 
       
       vis, 
       
       int
       
       & 
       
       m, 
       
       int
       
       & 
       
       n, 
       
       int
       
       & 
       
       k) {
       
       int 
       
       res 
       
       = 
       
       1;
       
       for (
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       4; 
       
       ++
       
       i) {
       
       int 
       
       x 
       
       = 
       
       nx 
       
       + 
       
       dx[
       
       i], 
       
       y 
       
       = 
       
       ny 
       
       + 
       
       dy[
       
       i];
       
       if (
       
       0 
       
       <= 
       
       x 
       
       && 
       
       x 
       
       < 
       
       m 
       
       && 
       
       0 
       
       <= 
       
       y 
       
       && 
       
       y 
       
       < 
       
       n 
       
       && 
       
       !
       
       vis[
       
       x][
       
       y] 
       
       && 
       
       countDigit(
       
       x, 
       
       y) 
       
       <= 
       
       k) {
       
       vis[
       
       x][
       
       y] 
       
       = 
       
       1;
       
       res 
       
       += 
       
       dfs(
       
       x, 
       
       y, 
       
       vis, 
       
       m, 
       
       n, 
       
       k);
       
            }
       
        }
       
       return 
       
       res;
       
    }
       
       int 
       
       movingCount(
       
       int 
       
       m, 
       
       int 
       
       n, 
       
       int 
       
       k) {
       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       > 
       
       > 
       
       vis(
       
       m, 
       
       vector
       
       <
       
       int
       
       >(
       
       n, 
       
       0));
       
       vis[
       
       0][
       
       0] 
       
       = 
       
       1;
       
       int 
       
       res 
       
       = 
       
       dfs(
       
       0, 
       
       0, 
       
       vis, 
       
       m, 
       
       n, 
       
       k);
       
       return 
       
       res;
       
    }
       
};
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.