66 机器人的运动范围

题目描述

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

解题思路

核心思想：DFS/BFS遍历。

时间复杂度：O(mn) 空间复杂度：O(mn)

Python 实现

def moving_count(threshold, rows, cols):
    """
    机器人能够到达的格子数

    Args:
        threshold: 阈值k
        rows: 行数
        cols: 列数

    Returns:
        int: 能够到达的格子数
    """
    if threshold < 0 or rows <= 0 or cols <= 0:
        return 0

    visited = [[False] * cols for _ in range(rows)]

    def digit_sum(num):
        """求数位之和"""
        s = 0
        while num:
            s += num % 10
            num //= 10
        return s

    def dfs(row, col):
        # 越界或已访问
        if row < 0 or row >= rows or col < 0 or col >= cols or visited[row][col]:
            return 0

        # 数位和超过阈值
        if digit_sum(row) + digit_sum(col) > threshold:
            return 0

        # 标记访问
        visited[row][col] = True

        # 四个方向
        count = 1 + dfs(row - 1, col) + dfs(row + 1, col) + \
                  dfs(row, col - 1) + dfs(row, col + 1)

        return count

    return dfs(0, 0)


# 测试代码
if __name__ == "__main__":
    print(f"k=18, 5行5列: {moving_count(18, 5, 5)}")
    print(f"k=10, 1行10列: {moving_count(10, 1, 10)}")

# 输出:
# k=18, 5行5列: 25
# k=10, 1行10列: 10