题目描述：
给定一个二维网络，给定任意起点与终点。每一步可以往4个方向走。要找出黄金最多的一条线路。
很明显的是要“一条路走到黑，一直下去直到某个条件停止”。
运用dfs（深度优先搜索）求解。
因为起点任意，所以从每个点开始搜，接着每个点又搜相邻点。反复如此。
递归的终止条件：
1：越界。
2：搜到已经走过的点也终止。
3：遇到黄金数量为0的点。
用一个形参变量sum存储每条线路的当前黄金数量。
每一次更新返回值res的值。
搜一个点先将其标记，再搜其4个方向相邻点，搜完相邻点后取消原标记。
解题代码：
1 class Solution { 2 public int res = -10000000; 3 public int max = 0 ; 4 public boolean[][] vis = new boolean[20][20]; 5 public int getMaximumGold(int[][] grid) { 6 for(int i = 0 ; i < grid.length;i++){ 7 for(int j = 0 ;j < grid[0].length;j++){ 8 dfs(grid,i,j,0); 9 } 10 } 11 return res; 12 } 13 public void dfs(int[][] grid,int i,int j,int sum){ 14 15 if(i<0||j<0||i>=grid.length||j>=grid[0].length||grid[i][j] == 0 || vis[i][j] ){ // 递归终止条件 16 return ; 17 } 18 vis[i][j] = true; // 标记 19 sum += grid[i][j]; // 更新返回值 20 res = Math.max(sum,res); 21 dfs(grid,i-1,j,sum); 22 dfs(grid,i,j-1,sum); 23 dfs(grid,i+1,j,sum); 24 dfs(grid,i,j+1,sum); 25 vis[i][j] = false; // 取消标记 26 27 } 28 }
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
