问题描述:你要开发一座金矿,地质学家已经探明了这座金矿中的资源分布,并用大小为m*n的网格grid进行了标注,每个单元格中的整数就表示这一单元格中的黄金数量;如果单元格是空的,那么就是0,为了使收益最大化,矿工需按一下规则来开采黄金:每当矿工进入一个单元,就会收集该单元中的所有黄金,矿工每次可以从当前位置向上下左右四个方向走,每个单元格只能被开采一次,不能开采(进入)黄金数目为0的单元格,矿工可以从任意一个黄金的单元格出发或者停止;
递归求解:外层大函数为网格循环,表示从哪一个格子开始进入,内层dfs使用used函数表征该网格是否被走过,在循环中遍历,若当前网格没有被走过,则更新used数组,进入下一个dfs中,有四种走法,若走不通直接进行添加到最大堆中
public void tranceBack(int[][] board,int [][]used,int row,int column,int size,PriorityQueue<Integer>maxHeap)
{
if(borad[i][j]==0||used[i][j]==true||row>board.length||row<0||column>board[0].length||column<0)
{
maxheap.add(size);
return;
}
used[row][column]=true;
tranceBack(borad,used,tow+1,column,size+borad[row][column],maxHeap);
tranceBack(borad,used,tow-1,column,size+borad[row][column],maxHeap);
tranceBack(borad,used,tow,column+1,size+borad[row][column],maxHeap);
tranceBack(borad,used,tow,column-1,size+borad[row][column],maxHeap);
used[row][column]=false;
}
public TranceBack(int [][] board)
{
PriorityQueue<Integer>maxHeap=new PriorityQueue<>((a,b)->b-a);
Boolean [][] used=new Boolean[board.length][board[0].length];
for(int i=0;i<used.length;i++)
{
Arrays.fill(used[i],false);
}
for(int i=0;i<board.length;i++)
{
for(int j=0;i<board[i].length;j++)
{
tranceBack(board,used,i,j,0,maxHeap);
}
}
return maxHeap.peek();
}