Dada una matriz de 1 con uno o varios rectángulos dentro representados por 0, devuelva las coordenadas de la esquina superior izquierda y la esquina inferior derecha.
Agregué mi código a continuación, que sigue un patrón DFS de gráfico de cuadrícula básico, pero no puedo entender cómo devolver las coordenadas sin aumentar el tiempo de ejecución general. Me encantaría un poco de ayuda si alguien pudiera ayudarme a cruzar la línea de meta.
const findCoordinates = (grid) => { const coordinates = []; // const visited = new Set(); for (let r = 0; r < grid.length; r++) { for (let c = 0; c < grid[0].length; c++) { const rectangle = dfs(grid, r, c, new Set()); if (rectangle) coordinates.push(rectangle); } } return coordinates; } const dfs = (grid, r, c, visited) => { if (invalidPos(grid, r, c)) return null; const pos = r + ',' + c; if (visited.has(pos)) return null; visited.add(pos); dfs(grid, r, c, visited); dfs(grid, r, c, visited); dfs(grid, r, c, visited); dfs(grid, r, c, visited); const rectangle = visited.entries(); // return [[rectangle[0].split(''), rectangle[2].split('')], [rectangle[rectangle.length - 2].split(''), rectangle[rectangle.length - 1].split('')]]; } const invalidPos = (grid, r, c) => { const invalidRow = r < 0 || r >= grid.length; const invalidCol = c < 0 || c >= grid[0].length; return invalidRow || invalidCol || grid[r][c] === 1; } const grid1 = [ [1,1,1,1,1], [1,0,0,1,1], [1,0,0,1,1], [1,1,1,1,1] ]; console.log(findCoordinates(grid1)); // should return [[[1,1],[2,2]]] const grid2 = [ [1,1,1,1,1], [1,0,0,1,1], [1,0,0,1,1], [1,1,1,1,0] ]; console.log(findCoordinates(grid2)); // should return [[[1,1],[2,2]],[[3,4],[3,4]]]