LeetCode 1219 黄金矿工(回溯法)

class Solution {public int getMaximumGold(int[][] grid) {}
}

解决:

1.哪些点可以作为起始点?
遍历数组,只要不是0的位置都可以作为起始点
2.寻找下一步位置的时候,如何判断走哪里
用一个相同大小的boolean数组来记录走过的位置**,走过的位置记为true**
3.下一个位置可以走哪里?
不可以走边,即i和j走到边界的时候
下一个位置不是0的地方
4.回溯法过程
进来先判断是否到达边界条件或者下一部可能要终止.
更新最大黄金数目
回溯走四个方向

	Integer result = 0;public int getMaximumGold(int[][] grid){//对于每一个不是0的位置都可以当作起始点作为开始的位置//用一个同样大的二维数组来记录走过的路线boolean[][] visit = new boolean[grid.length][grid[0].length];for(int i = 0;i < grid.length;i++){for(int j = 0;j < grid[0].length;j++){if(grid[i][j] != 0){backTrace(i,j,0,grid,visit);}}}	return result;}/*** i和j代表当前的位置,可以确定下一步要走的位置* cur代表目前为止的黄金数目* @param i* @param j* @param cur*/public void backTrace(int i,int j,int cur,int[][] grid,boolean[][] visit){//更新最大的黄金数目if((i < 0 || i > grid.length-1) || (j < 0 || j > grid[0].length-1)|| grid[i][j] == 0||visit[i][j]){result = Math.max(result, cur);return;}cur += grid[i][j];visit[i][j] = true;//接下来分别让其走四个方向.backTrace(i-1,j,cur,grid,visit);backTrace(i+1,j,cur,grid,visit);backTrace(i,j-1,cur,grid,visit);backTrace(i,j+1,cur,grid,visit);visit[i][j] = false;}