网站开发工程师项目经验怎么写,花都营销型网站,光明建网站的公司,图片制作软件免费下载题目链接
题目链接
题目描述
地上有一个 m 行和 n列的方格#xff0c;横纵坐标范围分别是 0∼m−1 和 0∼n−1。
一个机器人从坐标 (0,0) 的格子开始移动#xff0c;每一次只能向左#xff0c;右#xff0c;上#xff0c;下四个方向移动一格。
但是不能进入行坐标和列…题目链接
题目链接
题目描述
地上有一个 m 行和 n列的方格横纵坐标范围分别是 0∼m−1 和 0∼n−1。
一个机器人从坐标 (0,0) 的格子开始移动每一次只能向左右上下四个方向移动一格。
但是不能进入行坐标和列坐标的数位之和大于 k 的格子。
请问该机器人能够达到多少个格子
注意: 0m50 0n50 0k100 样例1 输入k7, m4, n5 输出20 样例2 输入k18, m40, n40 输出1484 解释当k为18时机器人能够进入方格35,37因为3537 18。 但是它不能进入方格35,38因为3538 19。
题目考察知识点
图论 深搜or光搜 当前节点可以达到的节点为上下左右四个方向
解题代码
深搜dfs
递归实现
class Solution {// 深度优先// 在确定完是否满足条件后[先加结果然后标为已走]然后再进行dfsint result;// 可以走的方向int dir[][] {{-1,0},{1,0},{0,1},{0,-1}};public int movingCount(int threshold, int rows, int cols){// 判断临界情况也就是rows和cols都为0if(rows 0 || cols 0){return 0;}// 判断是否走过boolean[][] used new boolean[rows][cols];result 0;// 判断0,0是否符合条件if(!judge(0,0,threshold)) return 0;result ;used[0][0] true;dfs(0, 0, rows, cols, threshold, used);return result;}// 深度优先public void dfs(int inow, int jnow, int rows, int cols, int threshold, boolean[][] used){for(int i 0; i 4; i ){int inext inow dir[i][0];int jnext jnow dir[i][1];if(inext 0 inext rows jnext 0 jnext cols){// 满足条件才进行下一个dfsif(used[inext][jnext]false judge(inext, jnext, threshold)){result ;used[inext][jnext] true;dfs(inext, jnext, rows, cols, threshold, used);}}}}// 是否满足条件public boolean judge(int i, int j, int threshold){int now 0;while(i ! 0){now i % 10;i i / 10;}while(j ! 0){now j % 10;j j / 10;}// 不满足if(now threshold){return false;}else{return true;}}
}注意注意
used数组是必须要有的标识一下当前哪些格子被判断过了判断临界条件 特别是哪个rows和cols都为0的情况 判断完是否符合条件再去进行dfs更容易
广搜bfs
队列实现 队列不为空的时候一直循环 符合条件的进入队列
class Solution {// 广度优先// 在确定完是否满足条件后[先加结果然后标为已走]然后再进队列int result;// 可以走的方向int dir[][] {{-1,0},{1,0},{0,1},{0,-1}};public int movingCount(int threshold, int rows, int cols){// 判断临界情况也就是rows和cols都为0if(rows 0 || cols 0){return 0;}// 判断是否走过boolean[][] used new boolean[rows][cols];result 0;bfs(rows, cols, threshold, used);return result;}// 广度优先public void bfs(int rows, int cols, int threshold, boolean[][] used){Dequeint[] deque new LinkedList();if(judge(0, 0, threshold)){deque.push(new int[]{0, 0});used[0][0] true;result ;}while(!deque.isEmpty()){int[] now deque.pop();int inow now[0];int jnow now[1];for(int i 0; i 4; i ){int inext inow dir[i][0];int jnext jnow dir[i][1];if(inext 0 inext rows jnext 0 jnext cols){// 满足条件才进入队列if(used[inext][jnext]false judge(inext, jnext, threshold)){result ;used[inext][jnext] true;deque.push(new int[]{inext, jnext});}}}}return;}// 是否满足条件public boolean judge(int i, int j, int threshold){int now 0;while(i ! 0){now i % 10;i i / 10;}while(j ! 0){now j % 10;j j / 10;}// 不满足if(now threshold){return false;}else{return true;}}
}
