A continuación se muestra mi código para encontrar el área máxima de las islas, pero por alguna razón seguía fallando en este caso de prueba: [[1],[1]]
No estoy del todo seguro de lo que está mal y he estado pensando en una posible solución usando este método. Estaba pensando que una posible razón por la que este código no funciona correctamente es debido a la naturaleza síncrona de JS cuando se llama a dfs() en el bucle for en la parte inferior.
var maxAreaOfIsland = function(grid) { let maxArea = 0 let currArea = 0 let dirs = [ [0,1], [1,0], [-1,0], [0,-1] ] function dfs(r,c){ if(grid[r][c] === 0) return currArea++ grid[r][c] = 0 for(let [row,col] of dirs){ let nr = r+row let nc = c+col if(nr<0 || nc< 0|| nr >= grid.length|| nc >= grid[0].length){ return } dfs(nr,nc) } } for(let i = 0; i < grid.length; i++){ for(let j = 0; j< grid[0].length; j++){ if(grid[i][j] === 1){ currArea = 0 dfs(i,j) if(currArea > maxArea){ maxArea = currArea } } } } return maxArea }; console.log(maxAreaOfIsland( [[1],[1]] ))Pruebe esto: supongo que debe verificar si la celda es válida en la cuadrícula antes de continuar.
var maxAreaOfIsland = function(grid) { let maxArea = 0 let currArea = 0 let dirs = [ [0,1], [1,0], [-1,0], [0,-1] ] function dfs(r,c){ if(r<0 || c< 0|| r >= grid.length|| c >= grid[0].length) return if(grid[r][c] === 0) return currArea++ grid[r][c] = 0 for(let [row,col] of dirs){ let nr = r+row let nc = c+col dfs(nr,nc) } } for(let i = 0; i < grid.length; i++){ for(let j = 0; j< grid[0].length; j++){ if(grid[i][j] === 1){ currArea = 0 dfs(i,j) if(currArea > maxArea){ maxArea = currArea } } } } return maxArea }; console.log(maxAreaOfIsland( [[1],[1]] ))Recomiendo usar C++ ya que el mismo código tardará 8 veces menos en comparación con JS
Parece como si la función dfs estuviera destinada a buscar en una ubicación distinta de cero, incrementando currArea a medida que encuentra más valores distintos de cero y teniendo cuidado de no salirse del borde de la matriz. Sin embargo, el return en esa verificación de límites abandona la búsqueda cuando debería continue . Un cambio, marcado con un comentario...
var maxAreaOfIsland = function(grid) { let maxArea = 0 let currArea = 0 let dirs = [ [0,1], [1,0], [-1,0], [0,-1] ] function dfs(r,c){ if(grid[r][c] === 0) return currArea++ grid[r][c] = 0 for(let [row,col] of dirs){ let nr = r+row let nc = c+col if(nr<0 || nc< 0|| nr >= grid.length|| nc >= grid[0].length){ continue; // <-- notice, we keep searching } dfs(nr,nc) } } for(let i = 0; i < grid.length; i++){ for(let j = 0; j< grid[0].length; j++){ if(grid[i][j] === 1){ currArea = 0 dfs(i,j) if(currArea > maxArea){ maxArea = currArea } } } } return maxArea }; console.log(maxAreaOfIsland( [[1],[1]] ))