# \[剑指Offer-13]\[中等]\[DFS] 机器人的运动范围

## 题目描述

[剑指 Offer 13. 机器人的运动范围](https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/)

地上有一个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。请问该机器人能够到达多少个格子？

示例 1：

```
输入：m = 2, n = 3, k = 1
输出：3
```

示例 2：

```
输入：m = 3, n = 1, k = 0
输出：1
```

提示：

* 1 <= n,m <= 100
* 0 <= k <= 20

## 解题思路

标准的DFS, 向四个方式搜索, 注意剪枝条件即可. 使用哈希表存储已经走过的格子, 配合剪枝, 以及完成总数量的统计.

```python
class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        seen = set()
        def dfs(i, j):
            if (i, j) in seen:
                return
            if not 0 <= i < m or not 0 <= j < n:
                return
            total = 0
            ti, tj = i, j
            while ti:
                total += ti - (ti // 10) * 10 if ti > 9 else ti
                ti = ti // 10
            while tj:
                total += tj - (tj // 10) * 10 if tj > 9 else tj
                tj = tj // 10
            if total > k:
                return

            seen.add((i, j))
            dfs(i - 1, j)
            dfs(i + 1, j)
            dfs(i, j - 1)
            dfs(i, j + 1)

        dfs(0, 0)
        return len(seen)
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blessbingo.gitbook.io/garnet/suan-fa/dfs/jian-zhi-offer13-ji-qi-ren-de-yun-dong-fan-wei.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.