• 题目难度：较难 😒

  • 题目描述：

    地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 threshold 的格子。 例如，当 threshold 为 18 时，机器人能够进入方格 [35,37] ，因为 3+5+3+7 = 18。但是，它不能进入方格 [35,38] ，因为 3+5+3+8 = 19 。请问该机器人能够达到多少个格子？
  • 数据范围： 0 ≤ threshold ≤ 15 ，1 ≤ rows,cols ≤ 100
  • 进阶：空间复杂度 O(nm) ，时间复杂度 O(nm)

  • 示例1:

    输入：1,2,3
    返回值：3

  • 示例2:

    输入：10,1,100
    返回值：29
    说明：[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[0,10],[0,11],[0,12],[0,13],[0,14],[0,15],[0,16],[0,17],[0,18],[0,19],[0,20],[0,21],[0,22],[0,23],[0,24],[0,25],[0,26],[0,27],[0,28] 这29种，后面的[0,29],[0,30]以及[0,31]等等是无法到达的

  • 思路：DFS

    提交结果：答案正确 运行时间：3ms 占用内存：524KB

    class Solution {
private:
  bool st[110][110];
  int dir[4][2] = {{-1,0}, {0, -1}, {1, 0}, {0, 1}};
  int curCheck = 0;
public:

  int cal(int x) {
      int res = 0;
      while (x) {
          int n = x % 10;
          res += n;
          x /= 10;
      }
      return res;
  }

  int movingCount(int threshold, int rows, int cols) {
      if(threshold <= 0) return 1;
      memset(st, false, sizeof st);
      dfs(0, 0, rows, cols, threshold);
      return curCheck;
  }

  void dfs(int x, int y, int rows, int cols, int threshold) {
      if(x < 0 || y < 0 || x >= rows || y >= cols || st[x][y]) return;
      if (cal(x) + cal(y) > threshold)  return;
      curCheck += 1;
      st[x][y] = true;

      for (int i = 0; i < 4; ++i) {
          dfs(x + dir[i][0], y + dir[i][1], rows, cols, threshold);
      }
  }
};

  • 思路二：BFS

    提交结果：答案正确 运行时间：3ms 占用内存：540KB

    class Solution {
private:
  int dir[4][2] = {{-1,0}, {0, -1}, {1, 0}, {0, 1}};
  bool st[110][110];
  int curCheck = 0;
  typedef pair<int, int> PII;
public:

  int cal(int x) {
      int res = 0;
      while (x) {
          int n = x % 10;
          res += n;
          x /= 10;
      }
      return res;
  }

  int movingCount(int threshold, int rows, int cols) {
      if (threshold <= 0) return 1;
      memset(st, false, sizeof st);

      queue<PII> q;
      q.push({0, 0});
      st[0][0] = true;

      while (!q.empty()) {
          auto temp = q.front();
          temp.pop();
          curCheck++;

          for (int i = 0; i <= 3; ++i) {
              int x = temp.first + dir[i][0];
              int y = temp.first + dir[i][1];

              if (x >= 0 && x < rows && y >= 0 && y < cols && !st[x][y]) {
                  if (cal(x) + cal(y) <= threshold) {
                      q.push({x, y});
                      st[x][y] = true;
                  }
              }
          }
      }
      return curCheck;
  }
};

    😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘