【算法设计】- 机器人的运动范围

做一个柔情的程序猿

共 2191字,需浏览 5分钟

 ·

2021-01-30 12:49




算法分析

机器人的运动范围

● ○ ●

The range of motion of the robot

● ○ ●

算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。 算法(Algorithm)是解题的步骤,可以把算法定义成解一确定类问题的任意一种特殊的方法。

❉❉❉❉❉❉❉❉❉❉




题目描述





地上有一个 m 行和 n 列的方格。一个机器人从坐标 (0, 0) 的格子开始移动,每一次只能向左右上下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于 k 的格子。

例如,当 k 为 18 时,机器人能够进入方格 (35,37),因为 3+5+3+7=18。但是,它不能进入方格 (35,38),因为 3+5+3+8=19。请问该机器人能够达到多少个格子?




解题思路





使用深度优先搜索(Depth First Search,DFS)方法进行求解。回溯是深度优先搜索的一种特例,它在一次搜索过程中需要设置一些本次搜索过程的局部状态,并在本次搜索结束之后清除状态。而普通的深度优先搜索并不需要使用这些局部状态,虽然还是有可能设置一些全局状态。

private static final int[][] next = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};private int cnt = 0;private int rows;private int cols;private int threshold;private int[][] digitSum;
public int movingCount(int threshold, int rows, int cols) { this.rows = rows; this.cols = cols; this.threshold = threshold; initDigitSum(); boolean[][] marked = new boolean[rows][cols]; dfs(marked, 0, 0); return cnt;}
private void dfs(boolean[][] marked, int r, int c) { if (r < 0 || r >= rows || c < 0 || c >= cols || marked[r][c]) return; marked[r][c] = true; if (this.digitSum[r][c] > this.threshold) return; cnt++; for (int[] n : next) dfs(marked, r + n[0], c + n[1]);}
private void initDigitSum() { int[] digitSumOne = new int[Math.max(rows, cols)]; for (int i = 0; i < digitSumOne.length; i++) { int n = i; while (n > 0) { digitSumOne[i] += n % 10; n /= 10; } } this.digitSum = new int[rows][cols]; for (int i = 0; i < this.rows; i++) for (int j = 0; j < this.cols; j++) this.digitSum[i][j] = digitSumOne[i] + digitSumOne[j];}

「❤️ 感谢大家」

如果你觉得这篇内容对你挺有有帮助的话:

  1. 点赞支持下吧,让更多的人也能看到这篇内容(收藏不点赞,都是耍流氓 -_-)
  2. 欢迎在留言区与我分享你的想法,也欢迎你在留言区记录你的思考过程。
  3. 觉得不错的话,也可以阅读近期梳理的文章(感谢各位的鼓励与支持🌹🌹🌹):

发现更多精彩

关注公众号



点分享

点点赞

点在看

浏览 19
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报