Dado un mapa de cuadrícula bidimensional de ‘1 (tierra) y’ 0 (agua), cuente el número de islas. Una isla está rodeada de agua y se forma conectando tierras adyacentes horizontal o verticalmente. Puede suponer que los cuatro bordes de la cuadrícula están rodeados de agua.
Ejemplo 1:
11110 11010 11000 00000
Respuesta 1
Solución Java 1 – DFS
La idea básica de la siguiente solución es fusionar tierras adyacentes, y la fusión debe realizarse de forma recursiva.
Cada elemento se visita una sola vez. Entonces el tiempo es O (m * n).
public int numIslands(char[][] grid) { if(grid==null || grid.length==0||grid[0].length==0) return 0; int m = grid.length; int n = grid[0].length; int count=0; for(int i=0; i<m; i++){ for(int j=0; j<n; j++){ if(grid[i][j]=='1'){ count++; merge(grid, i, j); } } } return count; } public void merge(char[][] grid, int i, int j){ int m=grid.length; int n=grid[0].length; if(i<0||i>=m||j<0||j>=n||grid[i][j]!='1') return; grid[i][j]='X'; merge(grid, i-1, j); merge(grid, i+1, j); merge(grid, i, j-1); merge(grid, i, j+1); } |
Solución Java 2: Union-Find
El tiempo es O (m * n * log (k)).
public int numIslands(char[][] grid) { if(grid==null || grid.length==0 || grid[0].length==0) return 0; int m = grid.length; int n = grid[0].length; int[] dx={-1, 1, 0, 0}; int[] dy={0, 0, -1, 1}; int[] root = new int[m*n]; int count=0; for(int i=0; i<m; i++){ for(int j=0; j<n; j++){ if(grid[i][j]=='1'){ root[i*n+j] = i*n+j; count++; } } } for(int i=0; i<m; i++){ for(int j=0; j<n; j++){ if(grid[i][j]=='1'){ for(int k=0; k<4; k++){ int x = i+dx[k]; int y = j+dy[k]; if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]=='1'){ int cRoot = getRoot(root, i*n+j); int nRoot = getRoot(root, x*n+y); if(nRoot!=cRoot){ root[cRoot]=nRoot; //update previous node's root to be current count--; } } } } } } return count; } public int getRoot(int[] arr , int i){ while(arr[i]!=i){ i = arr[arr[i]]; } return i; } |
Echa un vistazo a Number of Island II.
