題目描述：
給定一個二維網路，給定任意起點與終點，每一步可以往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 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/122734.html
標籤：其他