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

题目

地上有一个m行n列的方格。一个机器人从坐标(0,0)的格子开始移动，它每次可以向左、右、上、下移动一格，但不能进入行坐标和列坐标的数位之和大于k的格子。

例如，当k为18时，机器人能够进入方格（35，37），因为3+5+3+7=18。但它不能进入方格（35，38），因为3+5+3+8=19。请问该机器人能够到达多少个格子？

分析

方格可以看成一个m $\chi$ n的矩阵，在这个矩阵中，除边界的格子之外，其他格子都有4个相邻的格子。

机器人从坐标(0,0)开始移动，当它准备进入坐标(i,j)的格子时，通过检查坐标的数位来判断机器人是否能够进入。如果机器人能够进入坐标为(i,j)的格子，则再判断它能否进入4个相邻的格子(i,j-1)、(i-1,j)、(i,j+1)、(i+1,j)。能进入的格子总数=当前格子(1) + 来自上下左右递归后返回的计数。

C++算法实现

#include <iostream>
using namespace std;

int movingCountCore(int threshold, int rows, int clos, 
                    int row, int col, bool *visited);

bool check(int threshold, int rows, int clos, 
           int row, int clo, bool *visited);

int getDigitSum(int number);

// 计算移动的方格
int movingCount(int threshold, int rows, int clos)
{
    if (threshold < 0 || rows <= 0 || clos <= 0 )
        return 0;

    bool *visited = new bool[rows * clos];
    for (int i = 0; i < rows * clos; i++)
        visited[i] = false;

    int count = movingCountCore(threshold, rows, clos, 0, 0, visited);

    delete[] visited;
    return count;
}

int movingCountCore(int threshold, int rows, int cols,  int row, int col, bool *visited)
{
    int count = 0;
    // 当前方格是否能够进入
    if (check(threshold, rows, cols, row, col, visited))
    {
        visited[row * cols + col] = true;
        // 上下左右确认是否能够进入
        count = 1 + movingCountCore(threshold, rows, cols, row - 1, col, visited) +
        movingCountCore(threshold, rows, cols, row, col - 1, visited) +
        movingCountCore(threshold, rows, cols, row + 1, col, visited) +
        movingCountCore(threshold, rows, cols, row, col + 1, visited);
    }
    return count;
}

// 确认是否能够进入坐标(row, col)的方格
bool check(int threshold, int rows, int cols, int row, int col, bool *visited)
{
    //索引值在有效范围内、元素尚未访问、各位数和小于等于阈值
    if (row >= 0 && row < rows && col >=0 && col < cols
        && getDigitSum(row) + getDigitSum(col) <= threshold
        && !visited[row * cols + col])
        return true;
    return  false;
}

// 计算一个数字的数位之和
int getDigitSum(int number)
{
    int sum = 0;
    while (number > 0) {
        sum += number % 10;
        number /= 10;
    }
    return sum;
}

复杂度分析

时间复杂度

时间复杂度 O(rowsxcols)。

空间复杂度

建立了一个辅助空间布尔矩阵，空间复杂度为 O(rows*cols)。递归工作栈消耗 O(max(rows,cols))。

参考

<<剑指offer>>