黄金矿工（LeetCode Medium难度）1129题题解（DFS）

题目描述：

给定一个二维网络，给定任意起点与终点。每一步可以往4个方向走。要找出黄金最多的一条线路。

很明显的是要“一条路走到黑，一直下去直到某个条件停止”。

运用dfs（深度优先搜索）求解。

因为起点任意，所以从每个点开始搜，接着每个点又搜相邻点。反复如此。

递归的终止条件：

1：越界。

2：搜到已经走过的点也终止。

3：遇到黄金数量为0的点。

用一个形参变量sum存储每条线路的当前黄金数量。

每一次更新返回值res的值。

搜一个点先将其标记，再搜其4个方向相邻点，搜完相邻点后取消原标记。

解题代码：

 class Solution {

     public int res = -10000000;

     public int max = 0 ;

     public boolean[][] vis = new boolean[20][20];

     public int getMaximumGold(int[][] grid) {

         for(int i =  0 ; i < grid.length;i++){

             for(int j = 0 ;j < grid[0].length;j++){

                         dfs(grid,i,j,0);

             }

         }

         return res;

     }

     public void dfs(int[][] grid,int i,int j,int sum){

         if(i<0||j<0||i>=grid.length||j>=grid[0].length||grid[i][j] == 0 || vis[i][j] ){ // 递归终止条件

             return ;

         }

         vis[i][j] = true;   // 标记

         sum += grid[i][j];    // 更新返回值

         res = Math.max(sum,res);

         dfs(grid,i-1,j,sum);

         dfs(grid,i,j-1,sum);

         dfs(grid,i+1,j,sum);

         dfs(grid,i,j+1,sum);

         vis[i][j] = false; // 取消标记

     }

 }

巴特西

黄金矿工（LeetCode Medium难度）1129题题解（DFS）

最新文章

热门文章

巴特西

黄金矿工（LeetCode Medium难度）1129题 题解（DFS）

最新文章

热门文章

黄金矿工（LeetCode Medium难度）1129题题解（DFS）