机器人的运动范围

题目描述

地上有一个 m 行和 n 列的方格，横纵坐标范围分别是 0∼m−1 和 0∼n−1。

一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。

但是不能进入行坐标和列坐标的数位之和大于 k的格子。

请问该机器人能够达到多少个格子？

样例1

输入：k=7, m=4, n=5

输出：20

样例2

输入：k=18, m=40, n=40

输出：1484

解释：当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。

　　　但是，它不能进入方格（35,38），因为3+5+3+8 = 19。

注意:

    1. 0<=m<=50
    2. 0<=n<=50
    3. 0<=k<=100

思路

　　dfs，遇到一个能进入的方格ans就加1，然后判断它周围四个方向的格子能不能进入、之前有没有访问过，从而判断是否要进入并继续dfs，若它四个方向都不可行，那么就return，最后输出ans即可.

※温馨提示

　　1. 当m=0或n=0时，ans=0；

　　2. 若没有可行路径能到达格子p，那即便p的位数和小于k也没用，是到大不了的（一开始没注意到这点，所以直接二层循环，就错了QAQ）；

 1 class Solution {
 2 public:
 3     int d[4][2]={{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
 4     bool vis[55][55];
 5     int ans=0;
 6     
 7     void dfs(int k, int m, int n, int x, int y) {
 8         int xx=x, yy=y, sum=0;
 9         while(xx) {
10             sum+=xx%10;
11             xx/=10;
12         }
13         while(yy) {
14             sum+=yy%10;
15             yy/=10;
16         }
17         if(sum<=k) {
18             ans++;
19             vis[x][y]=true;
20             for(int i=0; i<4; i++) {
21                 int dx=x+d[i][0];
22                 int dy=y+d[i][1];
23                 if(dx>=0 && dx<m && dy>=0 && dy<n && !vis[dx][dy]) dfs(k, m, n, dx, dy);
24             }
25         }
26         return;
27     }
28     
29     int movingCount(int threshold, int rows, int cols)
30     {
31         if(rows>0 && cols>0)
32             dfs(threshold, rows, cols, 0, 0);
33         return ans;
34     }
35 };