# 13.机器人的运动范围

### 题目

地上有一个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：

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

示例 2：

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

提示：

```C++
1 <= n,m <= 100
0 <= k <= 20
```

来源：力扣（LeetCode）

链接：<https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof>

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

### 一、 分析

矩阵搜索问题一般有两种思路：

* 通过递归实现的`深度优先DFS`
  * 朝一个方向走到底，再回退
* 用过队列实现的`广度优先BFS`
  * 按照“平推”的方式向前搜索

### 二、 解法一： 深度优先及优化

![解法](/files/-Mespn9KpZ2kImYKAl7z)

```Swift
func movingCount(_ m: Int, _ n: Int, _ k: Int) -> Int {
    if m <= 0 || n <= 0 || k < 0 {
        return 0
    }
    var flags: [[Bool]] = Array(repeating: Array(repeating: false, count: n), count: m)
    return moveTo(0, 0, k, flags: &flags)
}
```

#### 2.1 核心递归逻辑

```Swift
func moveTo(_ x: Int, _ y: Int, _ k: Int, flags: inout [[Bool]]) -> Int {
    if (x < 0 || x >= flags.first?.count ?? 0) ||
        (y < 0 || y >= flags.count) ||
        (flags[y][x] == true) ||
        (digitSum(x) + digitSum(y) > k)
    {
        return 0
    }
    
    flags[y][x] = true
    
    let count = 1
        + moveTo(x + 1, y, k, flags: &flags)
        + moveTo(x - 1, y, k, flags: &flags)
        + moveTo(x, y + 1, k, flags: &flags)
        + moveTo(x, y - 1, k, flags: &flags)
    
    return count
}
```

#### 2.2 数位和函数

```Swift
func digitSum(_ num: Int) -> Int {
    var temp = num
    var result = 0
    while temp > 0 {
        result += temp % 10
        temp = Int(floor(Double(temp) / 10.0))
    }
    return result
}
```

#### 2.3 总结

* 时间复杂度
  * 最差O(m\*n)
* 空间复杂度
  * 最差O(m\*n)

### 三、 深度优先算法优化

在深度优先的解法中，我们才拆分为了`上下左右`四个方向的子问题。

但实际上本题只需要`右下`两个方向就可以，因为上左一定是走过的。

优化后的核心 `moveTo` 代码：

```Swift
func moveTo(_ x: Int, _ y: Int, _ k: Int, flags: inout [[Bool]]) -> Int {
    if (x < 0 || x >= flags.first?.count ?? 0) ||
        (y < 0 || y >= flags.count) ||
        (flags[y][x] == true) ||
        (digitSum(x) + digitSum(y) > k)
    {
        return 0
    }
    
    flags[y][x] = true
    
    let count = 1
        + moveTo(x + 1, y, k, flags: &flags)
        + moveTo(x, y + 1, k, flags: &flags)
    
    return count
}
```

> 可以发现减少了多余的计算效率提升了不少，这点如果在面试中注意到的话是个很好的加分项哦

![13](/files/-Mespn9LqTLbrhwgTiq2)

#### 思路回顾

* 设 `fn(x, y)` 代表从 `(x, y)` 开始能到的格子数
* 从左上角开始的那么我们可以转化一下
* 即：`fn(x, y) = fn(x + 1, y) + fn(x, y + 1)`

### 四、 解法二：广度优先

> `广度优先`解法理解相比`深度优先`不够直观

```Swift
func movingCount_bfs(_ m: Int, _ n: Int, _ k: Int) -> Int {
    var visited = Array(repeating: Array(repeating: false, count: n), count: m)
    var result = 0
    var queue:Array = [(0,0,0,0)]

    while !queue.isEmpty {
        let (y,x,si,sj) = queue.removeFirst()
        if y >= m || x >= n || k < si + sj || visited[y][x]{
            continue
        }
        visited[y][x] = true
        result = result + 1
        queue.append((y + 1, x, digitSum(y + 1), sj))
        queue.append((y, x + 1, si, digitSum(x + 1)))
    }
    return result
}
```

![03](/files/-Mespn9MGjQJR7kKiV2a)

#### 4.1 图解

> 来源[Krahets](https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/solution/mian-shi-ti-13-ji-qi-ren-de-yun-dong-fan-wei-dfs-b/)

![1](/files/-Mespn9O1rQ-14BfJgLt)

![2](/files/-Mespn9PW_-HjA76eyZG)

![3](/files/-Mespn9QL8OItWZwVMzN)

![4](/files/-Mespn9Rw8F-g-jAxTG6)

![5](/files/-Mespn9Su9RYqh0cECOS)

![6](/files/-Mespn9TeQlk2Y2y33Hp)

![7](/files/-Mespn9UbkG2Iu07n24w)

![8](/files/-Mespn9VYmCPKTPld5Kg)

![9](/files/-Mespn9WgU60EF4K33Ln)


---

# 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://ryukiedev.gitbook.io/wiki/shu-ju-jie-gou-yu-suan-fa/jian-zhi-offerswift/13.-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.