【图论刷题-1】剑指 Offer 13. 机器人的运动范围

谁借莪１个温暖的怀抱￠ 2022-09-04 09:53 116阅读 0赞

# 剑指 Offer 13. 机器人的运动范围 #

> 力扣题目 [地址][Link 1]

## 难度与标签 ##

**中等难度**

*  图
 *  递归
 *  广度优先

## 题目描述 ##

地上有一个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 1\\le n,m\\le 100 1≤n,m≤100
 *   0 ≤ k ≤ 20 0\\le k \\le 20 0≤k≤20

## 题目分析 ##

第一想法：遍历两个数组，找到符合条件的坐标就好了—— 那么这样想的话机器人一点戏份都没有了。

所以小小的坑在于：机器人不能跳跃，也就是说如果 `(9,9)` 到不了的话，可能导致 `(9,10)`也到不了。

因此不能基于坐标进行计算判定。

需要模拟机器人行走的过程，两个重要规则：

*  上下左右行走一个单位，不能跳跃；
 *  不走重复的路。

题目附加的条件就是：不走 `非法` 的路。

所以根据这三个条件写出递归的边界即可。

## 解题代码1——递归 ##

class Solution { 
    public:
        // 返回是否合法
        bool sum_bit_k (int m, int n, int k) { 
            int y = 0;
            while (m > 0) { 
                y += m%10;
                m /= 10;
            }
            while (n > 0) { 
                y += n%10;
                n /= 10;
            }
    
            return y <= k;
        }
        /* 递归部分 x,y 即希望去的坐标 visited 标记已经去的地方和不能去的地方 m, n, k 均为题目条件， */
        int travel (int x, int y, vector<vector<bool>>& visited,
                    int m, int n, int k) { 
            // 边界判定
            if (x < 0 || y < 0 || x >= m || y >= n) { 
                return 0;
            }
            // 去过的和非法的
            if (visited[x][y]) { 
                return 0;
            }
            // 没去过，不管合法与否都表示考虑过
            visited[x][y] = true;
            // 落脚点可以，继续travel
            if (sum_bit_k( x, y, k)) { 
                int sum = 1;
                sum += travel(x+1, y, visited, m, n, k);
                sum += travel(x, y+1, visited, m, n, k);
                sum += travel(x-1, y, visited, m, n, k);
                sum += travel(x, y-1, visited, m, n, k);
                return sum;
            }
            return 0;
        }
      
        int movingCount(int m, int n, int k) { 
            vector<vector<bool>> visited(m, vector<bool>(n));
            return travel(0,0,visited,m,n,k);
        }
    };

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NtaWxleWFuOQ_size_16_color_FFFFFF_t_70][]

*  时间复杂度为  O ( m × n ) O(m\\times n) O(m×n)
 *  空间复杂度为  O ( m × n ) O(m\\times n) O(m×n)

## 解题代码2——广度优先搜索 ##

> 来自官方题解的 [广度优先搜索][Link 2]。

直接查看代码：

class Solution { 
        // 计算 x 的数位之和
        int get(int x) { 
            int res=0;
            for (; x; x /= 10) { 
                res += x % 10;
            }
            return res;
        }
    public:
        int movingCount(int m, int n, int k) { 
            if (!k) return 1;
            queue<pair<int,int> > Q;
            // 向右和向下的方向数组
            int dx[2] = { 0, 1};
            int dy[2] = { 1, 0};
            vector<vector<int> > vis(m, vector<int>(n, 0));
            Q.push(make_pair(0, 0));
            vis[0][0] = 1;
            int ans = 1;
            while (!Q.empty()) { 
                auto [x, y] = Q.front();
                Q.pop();
                for (int i = 0; i < 2; ++i) { 
                    int tx = dx[i] + x;
                    int ty = dy[i] + y;
                    if (tx < 0 || tx >= m || ty < 0 || ty >= n || vis[tx][ty] || get(tx) + get(ty) > k) continue;
                    Q.push(make_pair(tx, ty));
                    vis[tx][ty] = 1;
                    ans++;
                }
            }
            return ans;
        }
    };

*  时间复杂度为  O ( m × n ) O(m\\times n) O(m×n)
 *  空间复杂度为  O ( m × n ) O(m\\times n) O(m×n)

## 解题代码3——递推 ##

class Solution { 
        int get(int x) { 
            int res=0;
            for (; x; x /= 10){ 
                res += x % 10;
            }
            return res;
        }
    public:
        int movingCount(int m, int n, int k) { 
            if (!k) return 1;
            vector<vector<int> > vis(m, vector<int>(n, 0));
            int ans = 1;
            vis[0][0] = 1;
            for (int i = 0; i < m; ++i) { 
                for (int j = 0; j < n; ++j) { 
                    if ((i == 0 && j == 0) || get(i) + get(j) > k) continue;
                    // 边界判断
                    if (i - 1 >= 0) vis[i][j] |= vis[i - 1][j];
                    if (j - 1 >= 0) vis[i][j] |= vis[i][j - 1];
                    ans += vis[i][j];
                }
            }
            return ans;
        }
    };

*  时间复杂度为  O ( m × n ) O(m\\times n) O(m×n)
 *  空间复杂度为  O ( m × n ) O(m\\times n) O(m×n)

## 总结 ##

这道题相对而言比较简单，在递归的时候只要理清楚递归的终止条件就比较简单了。

希望这个作为【图论刷题】的开始，慢慢刷题或者相关的好玩的东西，复习一下图论相关知识。

> Smileyan  
> 2021.8.12 21:06

[Link 1]: https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NtaWxleWFuOQ_size_16_color_FFFFFF_t_70]: /images/20220829/2866384d33254660b2e15b900477a835.png
[Link 2]: https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/solution/ji-qi-ren-de-yun-dong-fan-wei-by-leetcode-solution/