黄金矿工

• 题目
• 思路
• 代码
• 结果

题目

你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。

为了使收益最大化，矿工需要按以下规则来开采黄金：

每当矿工进入一个单元，就会收集该单元格中的所有黄金。
矿工每次可以从当前位置向上下左右四个方向走。
每个单元格只能被开采（进入）一次。
不得开采（进入）黄金数目为 0 的单元格。
矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。

题目传送门

思路

其实题意就是，从某个节点出发。可以走出一条路径，获取路径的最大值。这个时候，0是没有黄金的，所以就不可以走，可视为障碍物！
遍历整个数组。只要当前的位置不为0.就将其作为深搜的起点去进行搜索，这样子，每次搜索完总是能得到一条路径的值，就将其余当前答案进行比较，如果大于当前答案，那么就赋值给当前答案即可，直到每个不为0的节点都被遍历过，深搜结束，返回值即是答案！

代码

class Solution {int map[][]=new int[16][16]; 					// 全局地图int row=0;					 					// 数组的行int column=0;				 					// 数组的列int visited[][]=new  int[16][16];				// 标记数组int ans=0;										// 最终结果int direction[][]={{1,0},{0,1},{-1,0},{0,-1}};	// 方向数组public int getMaximumGold(int[][] grid) {row=grid.length;column=grid[0].length;// 取出全局地图for (int i=0;i<row;++i){for (int j=0;j<column;++j){// 初始化标记数组visited[i][j]=0;map[i][j]=grid[i][j];}}for (int i=0;i<row;++i){for (int j=0;j<column;++j){if (map[i][j]!=0) // 当前位置可以进行深搜{visited[i][j]=1;dfs(i,j,map[i][j]);visited[i][j]=0;}}}return ans;}private void dfs(int x, int y, int num){ans=ans>num?ans:num;int t_x=0;int t_y=0;for (int i=0;i<4;++i){t_x=x+direction[i][0];t_y=y+direction[i][1];if (check(t_x,t_y)){visited[t_x][t_y]=1;dfs(t_x,t_y,num+map[t_x][t_y]);visited[t_x][t_y]=0;}}}private boolean check(int a,int b){//   横坐标不越界        纵坐标不越界       等待搜索的点数值大于0（有黄金）    没有被访问过return a>=0 && a<row && b>=0 && b<column && map[a][b]>0 && visited[a][b]==0;}
}

结果

简单题，就不再赘述了！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！