# Leetcode 1219. Path with Maximum Gold
# DFS

Runtime: 20 ms
faster than 63.31%

Memory Usage: 36.2 MB
less than 94.78%

class Solution {
    // 四個 DFS 可以探尋的方向
    int[][] direction=new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    
    public int getMaximumGold(int[][] grid) {
        int result=0;
        
        /*
        陣列值 arr[i][j] 表示指定的是第 i 列第 j 行的值。在使用二維陣列物件時，注意 length 所代表的長度，
        陣列名稱後直接加上 length（如 arr.length），所指的是有幾列（Row）；指定索引後加上 length（如 arr[0].length），
        指的是該列所擁有的元素，也就是行（Column）數目。   */
        for(int r=0;r<grid.length;r++){
            for(int c=0;c<grid[0].length;c++){
                // 若非0，則深度探索
                if(grid[r][c]!=0){
                    result=Math.max(result, dfs(grid, r, c));
                }
            }
        }
        return result;
    }
    
    public int dfs(int[][] grid, int row, int col){
        int current=grid[row][col];
        int maxPath=0;
        
        // 已存入current，設為0以免走回頭路
        grid[row][col]=0;
        
        for(int[] dir : direction){
            int nextRow=row+dir[0], nextCol=col+dir[1];
            
            // 若下一步超出地圖，則跳過
            if(nextRow<0 || nextRow>=grid.length ||
              nextCol<0 || nextCol>=grid[0].length || grid[nextRow][nextCol]==0){ 
                continue;
            }
            else{
                // 遞迴去求出最深的路
                maxPath=Math.max(maxPath, dfs(grid, nextRow, nextCol));
            }
        }
        // 若不復原，會影響其他dfs路線的計算
        grid[row][col]=current;
        return current+maxPath;
    }
    
}

/*
        陣列值 arr[i][j] 表示指定的是第 i 列第 j 行的值。在使用二維陣列物件時，注意 length 所代表的長度，
        陣列名稱後直接加上 length（如 arr.length），所指的是有幾列（Row）；指定索引後加上 length（如 arr[0].length），
        指的是該列所擁有的元素，也就是行（Column）數目。   */

解題思維:
DFS=>深度優先搜尋法
典型DFS題目
###### tags: `DFS` `遞迴` `Array`