剑指offer-机器人的运动范围

题目描述

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

 1 class Solution {
 2 public:
 3     int ans = 1;
 4     int n,m;
 5     int d[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
 6     int k;
 7     int movingCount(int threshold, int rows, int cols)
 8     {
 9         k = threshold;
10         if(cols == 0 || threshold < 0)
11         {
12             return 0;
13         }
14         n = rows;
15         m = cols;
16         bool *vis = new bool[rows * cols];
17         memset(vis,0,rows*cols);
18         vis[0] = 1;
19         dfs(0,0,vis);
20         return ans;
21     }
22     void dfs(int x,int y,bool *vis)
23     {
24         for(int i = 0;i < 4; i++)
25         {
26             int dx = x + d[i][0];
27             int dy = y + d[i][1];
28             if(dx >= 0 && dx < n && dy >= 0 && dy < m && !vis[dx * m + dy])
29             {
30                 int a,b;
31                 a = getsum(dx);
32                 b = getsum(dy);
33                 if(a + b <= k)
34                 {
35                     ans ++;
36                     vis[dx * m + dy] = true;
37                     dfs(dx,dy,vis);
38                 }
39             }
40         }
41         return ;
42     }
43     int getsum(int x)
44     {
45         int sum = 0;
46         while(x)
47         {
48             sum += x % 10;
49             x /= 10;
50         }
51         return sum;
52     }
53     
54 };