广州机械网站建设外包,山东鑫泰建设集团网站,网络维修,广东微信网站推广哪家专业【问题描述】 [中等]
地上有一个m行n列的方格#xff0c;从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动#xff0c;它每次可以向左、右、上、下移动一格#xff08;不能移动到方格外#xff09;#xff0c;也不能进入行坐标和列坐标的数位之和…【问题描述】 [中等]
地上有一个m行n列的方格从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动它每次可以向左、右、上、下移动一格不能移动到方格外也不能进入行坐标和列坐标的数位之和大于k的格子。例如当k为18时机器人能够进入方格 [35, 37] 因为353718。但它不能进入方格 [35, 38]因为353819。请问该机器人能够到达多少个格子示例 1
输入m 2, n 3, k 1
输出3
示例 1输入m 3, n 1, k 0
输出1
提示
1 n,m 100
0 k 20
【解答思路】
题目分析:题意是一个人从00开始向走可以走四个方向它下一个走到的地方的坐标数位之和不超过k问这个人最多可以走多少个格子
1. DFS
从起点开始用深搜的方式遍历矩阵 只向下或者向右控制深搜边界的同时判断当前访问的位置数位和是否小于等于k需要一个标记数组记录每个位置的访问情况防止重复计算 时间复杂度O(N^2) 空间复杂度O(N)
class Solution {int m,n,k;
public int movingCount(int m, int n, int k) {this.mm;this.nn;this.kk;//标记访问过的位置boolean[][] visitednew boolean[m][n];return dfs(0,0,0,visited);
}/*** 深搜* param i 横坐标* param j 纵坐标* param sum 坐标数位和* param visited 标记数组* return*/
private int dfs(int i, int j, int sum, boolean[][] visited) {//如果 坐标越界 或者 数位和大于k 或者 已经访问过则停止当前方向的深搜if (im||jn||sumk||visited[i][j])return 0;//标记为已访问visited[i][j]true;//向下或者向右深搜return 1dfs(i1,j,sums(i1,j),visited)dfs(i,j1,sums(i,j1),visited);
}//计算数位和
public int sums(int x,int y){int ans0;while (x ! 0) {ansx%10;x/10;}while (y ! 0) {ansy%10;y/10;}return ans;
}}2. BFS(队列)
从起点开始用深搜的方式遍历矩阵 只向下或者向右控制深搜边界的同时判断当前访问的位置数位和是否小于等于k需要一个标记数组记录每个位置的访问情况防止重复计算 时间复杂度O(N) 空间复杂度O(N)
//时间复杂度O(mn)
public int movingCount(int m, int n, int k) {//队列保存坐标Queueint[] queuenew ArrayDeque();//标记数组boolean[][] visitednew boolean[m][n];//广搜queue.add(new int[]{0,0});int count0;visited[0][0]true;while (!queue.isEmpty()) {int[] poll queue.poll();count;//向下、向右寻找符合要求的位置入队并标记访问状态//不越界 并且 数位和小于等于k 并且 未访问过if (poll[0] 1 m sums(poll[0] 1, poll[1]) k!visited[poll[0]1][poll[1]]){queue.add(new int[]{poll[0]1,poll[1]});visited[poll[0]1][poll[1]]true;}if (poll[1] 1 n sums(poll[0], poll[1] 1) k!visited[poll[0]][poll[1] 1]){queue.add(new int[]{poll[0],poll[1]1});visited[poll[0]][poll[1]1]true;}}return count;
}
//计算数位和
public int sums(int x,int y){int ans0;while (x ! 0) {ansx%10;x/10;}while (y ! 0) {ansy%10;y/10;}return ans;
}
【总结】
1. BFS
确定递归参数终止条件标记数组记录每个位置的访问情况计数在递归回溯中 同广度
2. DFS
队列 出队后搜索符合条件入队终止条件标记数组记录每个位置的访问情况计数在所有相同深度出完队列之后
3. BFS DFS 分步思考 效果佳
4.100以内数之和
