알고리즘 공부
2020. 8. 20. 22:30
https://leetcode.com/problems/path-with-maximum-gold/
/**
* @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;
};