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

❤BFS

思路

将行列坐标数位之和＞k的格子作为障碍物，显然此为传统的搜索题目，优先选择BFS.
在搜索过程中，搜索方向可以缩小为右、下，进一步优化

算法

  • 创建队列用于存储已遍历过的点
  • 创建数组用于标记
  • 将（0,0）入列并标记，取出后，从该点并向右下搜索，直到队列为空

    实现

    ```cpp // 向右和向下的方向数组
    1.      int d[2][2]={{0,1},{1,1}};
    2.   vector<vector<int> > vis(m, vector<int>(n, 0));
    3.   Q.push(make_pair(0, 0));
    4.   vis[0][0] = 1;
    5.   int ans = 1;
    6.   while (!Q.empty()) {
    7.       auto [x, y] = Q.front();
    8.       Q.pop();
    9.       for (int i = 0; i < 2; ++i) {
    10.           int tx = d[i][0] + x,ty=d[i][1]+y;
    11.           if (tx < 0 || tx >= m || ty < 0 || ty >= n || vis[tx][ty] || get(tx) + get(ty) > k) continue;
    12.           Q.push(make_pair(tx, ty));
    13.           vis[tx][ty] = 1;
    14.           ans++;
    15.       }
    16.   }
  1. <a name="CJnBY"></a>
  2. ### 复杂度分析
  4. - 时间复杂度：O(NM)，考虑所有格子都被纳入那么搜索时一个格子最多被访问的次数为常数，所以时间复杂度为O(2MN)
  5. - 空间复杂度：O(NM)
  6. <a name="Pm5QL"></a>
  7. ## ❤DFS
  8. <a name="sv5bq"></a>
  9. ### 思路
  10. 考虑到方法一提到的搜索方向只需要朝下或者朝右，那么DFS便可以解决这个问题。
  12. - 定义 `vis[i][j]` 为 `(i, j)` 坐标是否可达，如果可达返回 `1`，否则返回 `0`。
  13. - 首先 `(i, j)` 本身需要可以进入，因此需要先判断 `i` 和 `j` 的数位之和是否大于 `k` ，如果大于的话直接设置 `vis[i][j]` 为不可达即可。否则，前面提到搜索方向只需朝下或朝右，因此 (i, j) 的格子只会从 (i - 1, j) 或者 (i, j - 1) 两个格子走过来（不考虑边界条件），那么 vis[i][j] 是否可达的状态则可由如下公式计算得到：
  15.         ![](https://cdn.nlark.com/yuque/__latex/d5881f2737ea152465a52f49d197a484.svg#card=math&code=vis%5Bi%5D%5Bj%5D%3Dvis%5Bi-1%5D%5Bj%5D%20or%20vis%5Bi%5D%5Bj-1%5D&height=26&width=318)
  18. <a name="KPkFb"></a>
  19. ### 实现
  20. ```cpp
  21.         vector<vector<int> > vis(m, vector<int>(n, 0));
  22.         int ans = 1;
  23.         vis[0][0] = 1;
  24.         for (int i = 0; i < m; ++i) {
  25.             for (int j = 0; j < n; ++j) {
  26.                 if ((i == 0 && j == 0) || get(i) + get(j) > k) continue;
  27.                 // 边界判断
  28.                 if (i - 1 >= 0) vis[i][j] |= vis[i - 1][j];
  29.                 if (j - 1 >= 0) vis[i][j] |= vis[i][j - 1];
  30.                 ans += vis[i][j];
  31.             }
  32.         }

复杂度分析

  • 时间复杂度：O(NM)，一共有o(mn)个状态需要计算，每个状态递推计算时间复杂度为o(1)
  • 空间复杂度：O(NM)