成都机械网站制作,物流的网站模板免费下载,diy在线定制网站系统,网站模块是啥问题描述#xff1a;你要开发一座金矿#xff0c;地质学家已经探明了这座金矿中的资源分布#xff0c;并用大小为m*n的网格grid进行了标注#xff0c;每个单元格中的整数就表示这一单元格中的黄金数量#xff1b;如果单元格是空的#xff0c;那么就是0#xff0c;为了使…问题描述你要开发一座金矿地质学家已经探明了这座金矿中的资源分布并用大小为m*n的网格grid进行了标注每个单元格中的整数就表示这一单元格中的黄金数量如果单元格是空的那么就是0为了使收益最大化矿工需按一下规则来开采黄金每当矿工进入一个单元就会收集该单元中的所有黄金矿工每次可以从当前位置向上下左右四个方向走每个单元格只能被开采一次不能开采(进入)黄金数目为0的单元格矿工可以从任意一个黄金的单元格出发或者停止
递归求解外层大函数为网格循环表示从哪一个格子开始进入内层dfs使用used函数表征该网格是否被走过在循环中遍历若当前网格没有被走过则更新used数组进入下一个dfs中有四种走法若走不通直接进行添加到最大堆中
public void tranceBack(int[][] board,int [][]used,int row,int column,int size,PriorityQueueIntegermaxHeap)
{
if(borad[i][j]0||used[i][j]true||rowboard.length||row0||columnboard[0].length||column0)
{
maxheap.add(size);
return;
}
used[row][column]true;
tranceBack(borad,used,tow1,column,sizeborad[row][column],maxHeap);
tranceBack(borad,used,tow-1,column,sizeborad[row][column],maxHeap);
tranceBack(borad,used,tow,column1,sizeborad[row][column],maxHeap);
tranceBack(borad,used,tow,column-1,sizeborad[row][column],maxHeap);
used[row][column]false;
}
public TranceBack(int [][] board)
{
PriorityQueueIntegermaxHeapnew PriorityQueue((a,b)-b-a);
Boolean [][] usednew Boolean[board.length][board[0].length];
for(int i0;iused.length;i)
{
Arrays.fill(used[i],false);
}
for(int i0;iboard.length;i)
{
for(int j0;iboard[i].length;j)
{
tranceBack(board,used,i,j,0,maxHeap);
}
}
return maxHeap.peek();
}
