Un mapa de cuadrícula 2d de m filas yn columnas se llena inicialmente con agua. Podemos realizar una operación addLand que convierte el agua en la posición (fila, col) en una tierra. Dada una lista de posiciones para operar, cuente el número de islas después de cada operación addLand. 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.
Solución Java
Use una matriz para rastrear el nodo principal de cada celda.
public List<Integer> numIslands2(int m, int n, int[][] positions) { int[] parent = new int[m * n]; Arrays.fill(parent,-1); ArrayList<Integer> result = new ArrayList<>(); int[] dx = {-1, 0, 1, 0}; int[] dy = {0, 1, 0, -1}; int count = 0; for (int[] position : positions) { count++; int idx = n * position[0] + position[1]; if (parent[idx] == -1) { parent[idx] = idx; } for (int k = 0; k < 4; k++) { int x = position[0] + dx[k]; int y = position[1] + dy[k]; int idxNeighbor = n * x + y; if (x >= 0 && x < m && y >= 0 && y < n && parent[idxNeighbor] != -1) { int p = getParent(parent, idxNeighbor); //set neighor's parent to be current idx if (parent[p] != idx) { parent[p] = idx; count--; } } } result.add(count); } return result; } private int getParent(int[] parent, int i) { while (parent[i] != i) { i = parent[i]; } return i; } |
Complejidad de tiempo O (k * log (m * n)), donde k es la longitud de las posiciones.
