【每日一题】Leetcode1219 黄金矿工
2022/2/5 23:13:02
本文主要是介绍【每日一题】Leetcode1219 黄金矿工,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目内容
你要开发一座金矿,地质勘测学家已经探明了这座金矿中的资源分布,并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量;如果该单元格是空的,那么就是 0。
为了使收益最大化,矿工需要按以下规则来开采黄金:
每当矿工进入一个单元,就会收集该单元格中的所有黄金。
矿工每次可以从当前位置向上下左右四个方向走。
每个单元格只能被开采(进入)一次。
不得开采(进入)黄金数目为 0 的单元格。
矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。
题目解释
每当矿工进入一个单元,代表着需要一个搜索格子的函数
每次可以从当前位置往上下左右四个方向走,说明需要一个方向数组。
不得开采黄金数目为0的单元格意味着如果遍历访问到格子值为0的值,则不能访问
可以从任意一个有黄金的单元格出发或者停止。意思就是需要枚举起始的元素值
在访问格子的同时。设置一个全局变量记录此格子的值
代码段
class Solution { int[][] grid; int m,n; int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}}; int ans = 0; public int getMaximumGold(int[][] grid) { this.n = grid.length; this.m = grid[0].length; this.grid = grid; //从任意格子出发,收集相关格子的值 for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(grid[i][j]!=0){ dfs(i,j,0); } } } return ans; } public void dfs(int i,int j,int gold){ gold += grid[i][j]; ans = Math.max(ans,gold); //在dfs之前,每个待访问的格子需要清零,然后方便在访问后,下一次从其他格子出发的时候访问路径上存在该格子,还能使用该格子的值 int rec = grid[i][j]; grid[i][j] = 0; for(int d=0;d<4;d++){ //旋转方向数组,往上下左右移动坐标 int nx = i + dir[d][0]; int ny = j + dir[d][1]; if(nx >=0 && nx<n && ny>=0 && ny<m && grid[nx][ny] >0 ){ dfs(nx,ny,gold); } } grid[i][j] = rec; } }
这篇关于【每日一题】Leetcode1219 黄金矿工的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升