13. 机器人的运动范围

文章目录

• • 剑指offer 13 机器人的运动范围
  • • 解法一：深度优先搜索（DFS）
    • 解法二：广度优先搜索（BFS）

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

示例 1：

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

示例 2：

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

提示：

1 <= n,m <= 100
0 <= k <= 20

解法一：深度优先搜索（DFS）

深度优先遍历(DFS)，通过判断该坐标是否越界、该坐标是否访问过、该坐标数位之和是否大于k来判断机器人能否进入该格子，不管能否进入，都将该格子标记为已访问，且退出当前调用栈后，不用回退标记数组的状态，因为本身就是要访问完所有能够访问到的格子。如果机器人能够进入坐标为(x,y)的格子，而后再判断机器人能否进入该坐标相邻的4个格子，直到所有能遍历到的格子都遍历结束。

注意： 有些格子机器人是遍历不到的，如k=0时， 不管m,n多大，机器人只能访问到（0,0），（0,1），（1,0）三个坐标，且只能到达（0,0）一个坐标，无法通过访问到的（0,1）和（1,0）扩散出去访问别的坐标，因为这两个坐标机器人无法到达，只是可以通过（0，0）访问到他们一次而已，即这里要区分访问和到达是不同的含义。

如下图中3×2的方格，机器人从（0,0）开始移动，由于k=0,故访问了（0,1）后，数位之和大于0，回溯到上一级栈（0,0）处，继续换个方向移动，访问（1,0）后发现同样数位之和大于0，又回溯到（0,0）处，此时发现没有方向可以移动了，整个dfs结束。另外的三个坐标（1,1）、（2，0）（2,1）根本就没有访问过。

但若让k=2,则按照上述思路思考，机器人可以访问到所有格子，只是（2,1）无法到达而已，但可以通过（1,1）或者（2,0）访问到，只是由于（2,1）数位之和为3大于2，机器人无法到达。

class Solution {private int count = 0;//count在递归中一直改变，故设置为成员变量public int movingCount(int m, int n, int k) {if(m < 0 || n < 0 ) return -1;boolean[][] isVisited = new boolean[m][n];//标记矩阵dfs(m,n,k,isVisited,0,0);return count;    }private void dfs(int m,int n,int k,boolean[][] isVisited,int x,int y){//坐标越界或者已经访问过，直接返回退出本次调用栈if(x < 0 || x >=m || y < 0 || y >= n || isVisited[x][y]) return ;isVisited[x][y] = true;//标记该坐标访问过了//当已经确认机器人可以进入该坐标之后，才需要从这坐标向四个方向扩散if(getSum(x,y) <= k){count++;//机器人可以进入该坐标，故计数加一，并从该坐标往四个方向扩散int[] dx = {-1,1,0,0};int[] dy = {0,0,-1,1};for(int i = 0;i < 4;i++){//按照左、右、上、下四个方向扩散访问int a = x + dx[i];int b = y + dy[i];dfs(m,n,k,isVisited,a,b);}}else{return ;//机器人无法到达该坐标，故直接退出本次调用栈，返回上一级调用栈}}//计算行坐标和列坐标的数位之和private int getSum(int x,int y){int res = 0;while(x > 0){res += x % 10;x /= 10;}while(y > 0){res += y % 10;y /= 10;}return res;}
}

解法二：广度优先搜索（BFS）

class Solution {private int count = 0;public int movingCount(int m, int n, int k) {if(m < 0 || n < 0 ) return -1;boolean[][] isVisited = new boolean[m][n];//标记矩阵Queue<int[]> queue = new LinkedList<>();queue.add(new int[]{0,0});isVisited[0][0] = true;while(!queue.isEmpty()){int[] point = queue.poll();int x = point[0];int y = point[1];//当已经确认机器人可以进入该坐标之后，才需要从这坐标向四个方向扩散if(getSum(x,y) <= k){count++;//机器人可以进入该坐标，故计数加一，并从该坐标往四个方向扩散int[] dx = {-1,1,0,0};int[] dy = {0,0,-1,1};for(int i = 0;i < 4;i++){int a = x + dx[i];int b = y + dy[i];//坐标没有越界并且还没有访问过if(a >= 0 && a < m && b >= 0 && b < n && !isVisited[a][b]){queue.add(new int[]{a,b});isVisited[a][b] = true;}}}}  return count;    }//计算行坐标和列坐标的数位之和private int getSum(int x,int y){int res = 0;while(x > 0){res += x % 10;x /= 10;}while(y > 0){res += y % 10;y /= 10;}return res;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！