Ex13 机器人的运动范围

题目描述

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

问题分析

其实这个问题和Ex12 矩阵中的路径很相似，最主要的两点是：

• 需要一个visited数组；
• 只需要向右、下两个方向来寻找。

代码

int recursive_count (bool **visited, int m, int n, int i, int j, int k);
bool calculate (int i, int j, int k);

int
movingCount (int m, int n, int k)
{
  bool **visited = (bool **)malloc (m * sizeof (bool *));
  for (int i = 0; i < m; ++i)
    {
      visited[i] = (bool *)malloc (n * sizeof (bool));
    }
  for (int i = 0; i < m; ++i)
    {
      for (int j = 0; j < n; ++j)
        {
          visited[i][j] = false;
        }
    }

  int count = 0;
  count = recursive_count (visited, m, n, 0, 0, k);

  for (int i = 0; i < m; ++i)
    {
      free (visited[i]);
    }
  free (visited);

  return count;
}

int
recursive_count (bool **visited, int m, int n, int i, int j, int k)
{
  if ((i < 0 || i >= m) || (j < 0 || j >= n) || visited[i][j])
    return 0;
  if (!calculate (i, j, k))
    return 0;
  visited[i][j] = true;
  return 1 + recursive_count (visited, m, n, i + 1, j, k)
         + recursive_count (visited, m, n, i, j + 1, k);
}

bool
calculate (int i, int j, int k)
{
  int count = 0;
  while (i || j)
    {
      count += i % 10;
      i /= 10;
      count += j % 10;
      j /= 10;
    }
  return count <= k;
}

结果

执行结果：通过

执行用时：0 ms, 在所有 C 提交中击败了100.00%的用户

内存消耗：6 MB, 在所有 C 提交中击败了12.60%的用户