Dada una matriz de tamaño [matemática] m \ veces n [/ matemática] que contiene solo unos y ceros, ¿puedes encontrar cuántos grupos de unos hay?

Answer 1

Esto se puede hacer mediante una simple búsqueda bfs o dfs. Otra forma que sugirió Miguel Oliveira es contar la cantidad de componentes conectados

Aquí está mi enfoque.

public int countNumberOfOnes (char [] [] grid) {

if (grid == null || grid.length == 0) {
devuelve 0;
}
int M = grid.length;
int N = grid [0] .length;
int cuenta = 0;
booleano [] [] visitado = nuevo booleano [M] [N];

para (int fila = 0; i <M; fila ++) {
para (int col = 0; col <N; col ++) {
if (! visitó [fila] [col] && grid [fila] [col] == ‘1’) {
visita (cuadrícula, fila, columna, visitado);
recuento ++;
}
}
}
cuenta de retorno;
}

visita privada vacía
char [] [] grid, int row, int col, boolean [] [] visitado) {

visitado [fila] [col] = verdadero;

// mueve una fila debajo
if (isSafe (fila + 1, col, visitado, cuadrícula)) {
visita (cuadrícula, fila + 1, col, visitado);
}
// mueve una fila hacia atrás
if (isSafe (fila-1, col, visitado, cuadrícula)) {
visita (cuadrícula, fila-1, col, visitado);
}
// mover un frente de col
if (isSafe (fila, col + 1, visitado, cuadrícula)) {
visita (cuadrícula, fila, col + 1, visitado);
}
// mueve una columna detrás
if (isSafe (fila, col-1, visitado, cuadrícula)) {
visita (cuadrícula, fila, col-1, visitado);
}

}

booleano privado isSafe
(int row, int col, boolean [] [] visitado, char [] [] grid) {

fila de retorno> = 0
&& col> = 0
&& fila <grid.length
&& col <grid [0] .length
&&! visitó [fila] [col]
&& grid [fila] [col] == ‘1’;
}

Answer 2

Este es un problema estándar de relleno de inundación.

Tanto la Búsqueda de profundidad primero como la Búsqueda de profundidad primero trabajan para encontrar las ‘islas’ disjuntas de las mismas. Sin embargo, DFS puede tener problemas de desbordamiento de pila con matrices grandes. BFS tiende a ser preferible.

Answer 3

Entonces si te entiendo correctamente

todos los 1s en una fila o una línea están agrupados y un bloque como este también sería un grupo:

[matemáticas] \ begin {pmatrix} \ color {green} {1} & \ color {green} {\ cdots} & \ color {green} {1} y 0 \ cdots \\\ color {green} {1} & \ color {green} {\ cdots} y \ color {green} {1} y 0 \ cdots \\\ color {green} {\ vdots} y \ color {green} {\ ddots} y \ color {green} { \ vdots} & 0 \ cdots \\\ color {green} {1} & \ color {green} {\ cdots} & \ color {green} {1} y 0 \ cdots \\ 0 & 0 & 0 & \ ddots \ end {pmatrix} [/ math]

¿Derecho?

Bueno, suponiendo que tenga la matriz como doble int-array. Haría algo como esto

/ * Un pequeño ayudante para guardar los índices cuando los necesitemos * /
Índice de clase {
inicio privado int;
privado int fin;
línea int privada;
boolean privado emparejado;

Índice público (int start, int fin, int line) {
this.start = inicio;
this.fin = fin;
this.line = line;
this.matched = false;
}

// Getter para todos los parámetros, para emparejar también un setter.

/ *
* Dos índices pueden coincidir cuando son
* en la siguiente línea de cada uno y aún no coincide.
* /
public boolean canBeMatchedWith (Index otherIndex) {
if (otherIndex.getMatched ()) devuelve falso;
int ostart = otherIndex.getStart ();
int ofin = otherIndex.getFin ();
int oline = otherIndex.getLine ();
if ((olina = línea + 1 || olina = línea-1)
&&! (ostart> fin) &&! (ofin emparejado = verdadero;
otherIndex.setMatched (true);
volver verdadero;
}
}
}

// Programa principal
int [] [] matriz = int [m] [n];
// rellena o genera la matriz
fetiche booleano = falso; / * nos damos cuenta cuando
comenzamos a recoger 1s en una línea * /
List lind = new ArrayList <> ();
List > lindList = new ArrayList <> ();
int inicio = 0;
para (int i = 0; i para (int j = 0; j if (! fetchingOnes && matrix [i] [j] == 1) {
fetchingOnes = true;
inicio = i;
}
if (fetchingOnes && matrix [i] [j] == 0) {
fetchingOnes = false;
lind.add (nuevo índice (inicio, i, j));
}
}
lindList.add (lind);
lind = new ArrayList ();
}
/ *
* Ahora haga coincidir los índices de la línea k (1-m-1), paso 2
(con la línea k-1, línea = índice en lindList) que
reste los índices coincidentes del total de índices. * /

Espera que esto ayude.