侧边栏壁纸
博主头像
Lin2J博主等级

升级了服务器,访问应该会更加流畅🇨🇳

  • 累计撰写 94 篇文章
  • 累计创建 39 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

13 机器人的运动范围

Lin2J
2021-07-21 / 0 评论 / 0 点赞 / 111 阅读 / 1,288 字 / 正在检测是否收录...

剑指 Offer 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。请问该机器人能够到达多少个格子?

解题思路:

可以使用深度优先搜索剪枝法来做。

  • 深度优先搜索:通过递归,往一个方向一直搜索下去,统计格子数,如果格子不符合要求,则结束递归。然后往另一个方向进行搜索。
  • 剪枝法:当发现某个各自不符合要求时,就可以提前结束递归。

DFS 函数

递归参数:当前格子位置 $(x, y)$ 、整个方格的边界 $(m, n)$、数位和限制 $k$、方格遍历统计数组 $visited$。

终止条件:$x$ 或者 $y$ 越界、或者方格已经遍历过、或者 $x$ 和 $y$ 的数位和大于 $k$。

递推工作

  • 将 $visted[x][y]$ 置为 $true$,表示已经遍历过。
  • 可达到格子数 $count$ 加一。
  • 搜索下一个单元格,往右、下方向搜索。

代码:

int ans = 0;
public int movingCount(int m, int n, int k) {
    boolean[][] visited = new boolean[m][n];
    move(m, n, 0, 0, k, visited);
    return ans;
}

private void move(int m, int n, int x, int y, int k, boolean[][] visited){
    // 注意参数边界判断
    if(x >= m || y >= n || x < 0 || y < 0
            || visited[x][y] || !valid(x, y, k)){
        return ;
    }
    visited[x][y] = true;
    ans++;
    move(m, n, x+1, y, k, visited);
    move(m, n, x, y+1, k, visited);
}

/**
 * 判断 x 和 y 的数位和符合要求
 * @return 符合返回 true,否则返回 false
 */
private boolean valid(int x, int y, int k){
    return k >= (sumOfDigital(x) + sumOfDigital(y));
}

/**
 * 计算数位和
 */
private int sumOfDigital(int n){
    int sum = 0;
    while(n != 0){
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

复杂度分析

  • 时间复杂度 $O(MN)$:最多只需要遍历 $MN$ 个方格。
  • 空间复杂度 $O(MN)$:需要辅助数组 $visited$ ,空间为 $O(MN)$。
0

评论区