알고리즘 공부 2020. 8. 20. 22:30

https://leetcode.com/problems/path-with-maximum-gold/

 

Path with Maximum Gold - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

/**
 * @param {number[][]} grid
 * @return {number}
 */

var getMaximumGold = function(grid) {
    var maximum = 0;
    var grid2 = [];
    var visited=[];
    var i=0;
    var direction_y = [ -1,1,0,0 ];
    var direction_x = [ 0,0,-1,1 ]; 
    
    for( i=0; i<17; ++i )
    {
        grid2[i] = [];
        visited[i] = [];
        for( var j=0; j<17; ++j )
        {            
            grid2[i][j] = 0;            
            visited[i][j]=0;
        }
    }
    
    for( i=0; i<grid.length; ++i )
    {        
        for( var j=0; j<grid[0].length; ++j )
        {            
            grid2[i+1][j+1] = grid[i][j];
        }
    }    
    
    var find = function( p_y, p_x, p_visited, p_sum )
    {        
        if( grid2[p_y][p_x] != 0 )        
        {
            if( p_sum + grid2[p_y][p_x] > maximum )            
                maximum = p_sum + grid2[p_y][p_x];            
            
            for( var i=0; i<4; ++i )
            {
                const y = direction_y[i] + p_y;
                const x = direction_x[i] + p_x;
                
                if( y>0 && x>0 && y-1<visited.length && x-1<visited[0].length )
                {
                    if( p_visited[y-1][x-1] == 0  )
                    {
                        p_visited[y-1][x-1] = 1;                        
                        find( y, x, p_visited, p_sum+grid2[p_y][p_x] )
                        p_visited[y-1][x-1] = 0;
                    }
                }
            }
        }
    }
        
    for( var i=0; i<grid.length; ++i )
    {     
        for( var j=0; j<grid[0].length; ++j )
        {
            if( grid2[i+1][j+1] != 0 )
            {
                visited[i][j]=1;            
                find(i+1,j+1,visited,0);
                visited[i][j]=0;
            }
        }
    }
    return maximum;
};
posted by Sense.J
: