java leetcode之[图 中等]剑指 Offer 13. 机器人的运动范围
2021/9/15 17:04:52
本文主要是介绍java leetcode之[图 中等]剑指 Offer 13. 机器人的运动范围,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目的链接在这里:https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
目录
- 题目大意
- 一、示意图
- 二、解题思路
- 递归
- DFS
- BFS
题目大意
地上有一个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 BFS
递归
代码如下:
class Solution { boolean [][] visited; //然后是记录格子数的吧 // static int step; public int movingCount(int m, int n, int k) { //直接初始化 visited=new boolean[m][n]; return dfs(0,0,visited,k,m,n); } //其实是使用了递归 private int dfs(int i, int j, boolean[][] visited, int k, int m, int n) { //然后这里开始判断 if(i<0||i>=m||j<0||j>=n||(getNum(i)+getNum(j)>k)||visited[i][j]){ //满足这个条件的 return 0; } //不然的话 就判断他的四周 并说明这个点本身就是可以的 还需要再加一 visited[i][j]=true; return dfs(i+1,j,visited,k,m,n)+dfs(i-1,j,visited,k,m,n)+dfs(i,j+1,visited,k,m,n)+dfs(i,j-1,visited,k,m,n)+1; } private int getNum(int i) { //要么就是写一个方法来求 i和j的数位合 /* if(i<10){ return i; }*/ if(i>=10&&i<=99){ int temp1=i/10; int temp2=i%10; return temp1+temp2; } return i; } }
DFS
代码如下:
class Solution { //坑定有个矩阵用来判断这个位置有没有走过 boolean [][] visited; //然后是DFS int x[]={0,0,-1,1}; int y[]={1,-1,0,0}; int count; public int movingCount(int m, int n, int k) { //直接初始化 visited=new boolean[m][n]; count=0; //然后遍历第一个 并开始积累 dfs(0,0,m,n,k,visited); return count; } private void dfs(int i, int j, int m, int n, int k, boolean[][] visited) { //先进行判断 if(i>=m||j>=n) return; //然后判断是不是满足 if(i>=0&&i<m&&j>=0&&j<n&&!visited[i][j]&&(getNum(i)+getNum(j)<=k)){ //说明这个点是满足的 count++; visited[i][j]=true; //然后遍历他的其他的 这边就不能用for循环 for(int l=0;l<4;l++){ dfs(i+x[l],j+y[l],m,n,k,visited); } } } private int getNum(int i) { //要么就是写一个方法来求 i和j的数位合 /* if(i<10){ return i; }*/ if(i>=10&&i<=99){ int temp1=i/10; int temp2=i%10; return temp1+temp2; } return i; } }
BFS
代码如下:
class Solution { //坑定有个矩阵用来判断这个位置有没有走过 boolean [][] visited; //然后是DFS int x[]={0,0,-1,1}; int y[]={1,-1,0,0}; int count; public int movingCount(int m, int n, int k) { //BFS的话 就是进栈 站内应该是一个 m和n组成的吧 visited=new boolean[m][n]; Queue<List<Integer>> queue=new LinkedList<>(); List<Integer> list=new ArrayList<>(); list.add(0); list.add(0); //然后就开始判断他周围的 queue.add(list); count=0; visited[0][0]=true; while (!queue.isEmpty()){ //取出栈顶元素 List<Integer> poll = queue.poll(); //然后取出栈顶元素中的两个值 int i=poll.get(0); int j=poll.get(1); // visited[i][j]=true; //然后count++ 每次出栈都记录一下就行了 count++; //然后判断这个点的相邻点符不符合条件 for(int l=0;l<4;l++){ int new_i=i+x[l]; int new_j=j+y[l]; //然后进行判断 if(new_i>=0&&new_i<m&&new_j>=0&&new_j<n&&!visited[new_i][new_j]&&(getNum(new_i)+getNum(new_j)<=k)){ //满足条件的话 就进队列 List<Integer> temp=new ArrayList<>(); //会导致 1 1出现两次 所有应该在这就设置为true temp.add(new_i); temp.add(new_j); visited[new_i][new_j]=true; queue.add(temp); } } } return count; } private int getNum(int i) { //要么就是写一个方法来求 i和j的数位合 /* if(i<10){ return i; }*/ if(i>=10&&i<=99){ int temp1=i/10; int temp2=i%10; return temp1+temp2; } return i; } }
这篇关于java leetcode之[图 中等]剑指 Offer 13. 机器人的运动范围的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?