# 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`
  * 按照“平推”的方式向前搜索

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

![解法](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI8JgbGh3U6X_oedqkm%2Fsync%2Fb63ba8df6290b829ca523161e7b49b1d4a857cc4.png?generation=1626598752688427\&alt=media)

```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](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI8JgbGh3U6X_oedqkm%2Fsync%2F5128087494ee5eed24e6648365678be91d2c2b6f.png?generation=1626598757714252\&alt=media)

#### 思路回顾

* 设 `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](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI8JgbGh3U6X_oedqkm%2Fsync%2F4534584d6482cbe00d13de094200687f8519be6d.png?generation=1626598761682630\&alt=media)

#### 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](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI8JgbGh3U6X_oedqkm%2Fsync%2F5f53f57b445803133fab709606c9b0e546e74379.png?generation=1626598762745267\&alt=media)

![2](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI8JgbGh3U6X_oedqkm%2Fsync%2Fc7db1208ae8c4cfe3aa937348d7a87f554e21fcb.png?generation=1626598755728234\&alt=media)

![3](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI8JgbGh3U6X_oedqkm%2Fsync%2F2e3b0f6e5e3e3b80ae98ee64760e7216f1a1657f.png?generation=1626598763710878\&alt=media)

![4](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI8JgbGh3U6X_oedqkm%2Fsync%2F077bd3b3881ae294af56da4c4d3ed488f894f1f1.png?generation=1626598760683741\&alt=media)

![5](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI8JgbGh3U6X_oedqkm%2Fsync%2F5f7d08a83776ba3fa1a8ece25c7868f83de14ed8.png?generation=1626598754773323\&alt=media)

![6](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI8JgbGh3U6X_oedqkm%2Fsync%2F1ffb9ad7d0558d4202239e04f93f1b25b311c33a.png?generation=1626598758703822\&alt=media)

![7](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI8JgbGh3U6X_oedqkm%2Fsync%2Ff2d6a3fc1d28d4f8a923ae89885dd98ed9fb7f0c.png?generation=1626598759779610\&alt=media)

![8](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI8JgbGh3U6X_oedqkm%2Fsync%2Fc80b12e44d1feb36baaeed3f277b4048c91a85d6.png?generation=1626598753747765\&alt=media)

![9](https://4193904735-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI8JgbGh3U6X_oedqkm%2Fsync%2F68671a355a033b1fe80d4b62c36b1a64c357fa03.png?generation=1626598756766132\&alt=media)