题解 | #机器人的运动范围#

机器人的运动范围：最直观的想法是，使用一个divide数组保存数字的数位和，使用一个dp数组保存元素是否被访问过，然后从下标[0,0]开始进行dfs遍历。其中dfs遍历的过程如下，首先是处理不合法下标以及不合法数位和以及重复访问，然后是标记访问并且计算当前结果res并返回，其计算公式为上下左右四个方向的dfs结果加上当前该元素的访问之和。如果内存超出限制的话，检查一下是否是没有标记访问，从而导致的重复访问。

int dfs(vector<vector<bool>>& dp, vector<int>& divide, int threshold, int rows,
int cols, int i, int j) 
{
   if (i < 0 || i > rows - 1 || j < 0 || j > cols - 1 ||(divide[i] + divide[j])  	> threshold || dp[i][j]) //处理不合法
   return 0;
   dp[i][j] = true;
   int res = dfs(dp, divide, threshold, rows, cols, i + 1, j)+dfs(dp, divide,  	  threshold, rows, cols, i - 1, j)+dfs(dp, divide, threshold, rows, cols, i, j 	  + 1)+dfs(dp, divide, threshold, rows, cols, i, j - 1)+ 1;
   return res;
}
int movingCount(int threshold, int rows, int cols) 
{
   int maxn = rows > cols ? rows : cols;
   vector<int> divide(maxn + 1, 0);
   vector<vector<bool>> dp(rows, vector<bool>(cols, false));
   int s, k, n;
   for (int i = 0; i <= maxn; i++) 
   {
      s = 0;
      n = i;
      while (n) 
      {
         k = n % 10;
         s += k;
         n = n / 10;
      }
      divide[i] = s;
    }
    return dfs(dp, divide, threshold, rows, cols, 0, 0);
}