può contare le regioni contigue in una bitmap da migliorare su O (r * c)?

Question

Viene visualizzata un'immagine di una superficie fotografata da un satellite. L'immagine è una bitmap in cui l'acqua è contrassegnata da "." e la terra è contrassegnata da '*'. Il gruppo adiacente di "*" forma un'isola. (Due '*' sono adiacenti se sono vicini orizzontali, verticali o diagonali). Il tuo compito è stampare il numero di isole nella bitmap.

Esempio Ingresso: -

.........** 
**......*** 
........... 
...*....... 
*........*. 
*.........* 

uscita: - 5

Qui, è la mia realizzazione che prende O(r * c) spazio e O(r * c) spazio dove r è totale. di righe ec è il numero totale di colonne.

#include <stdio.h> 
#define COLS 12 

void markVisted(char map[][COLS], int visited[][COLS], int row, int col, int rowCount) 
{ 
    if((row < 0) || (row >= rowCount) || (col < 0) || (col >= COLS) || (map[row][col] != '*') || (visited[row][col] == 1)) return; 

    visited[row][col] = 1; 

    //calling neighbours 
    markVisted(map, visited, row+1, col, rowCount); 
    markVisted(map, visited, row, col+1, rowCount); 
    markVisted(map, visited, row-1, col, rowCount); 
    markVisted(map, visited, row, col-1, rowCount); 
    markVisted(map, visited, row+1, col+1, rowCount); 
    markVisted(map, visited, row-1, col-1, rowCount); 
    markVisted(map, visited, row-1, col+1, rowCount); 
    markVisted(map, visited, row+1, col-1, rowCount); 
} 
int countIslands(char map[][COLS], int visited[][COLS], int rowCount) 
{ 
    int i, j, count = 0; 
    for(i=0; i<rowCount; ++i){ 
     for(j=0; j<COLS; ++j){ 

      if((map[i][j] == '*') && (visited[i][j] == 0)){ 
       ++count; 
       markVisted(map, visited, i, j, rowCount); 
      } 
     } 
    } 
    return count; 
} 

int main() 
{ 
    char map[][COLS] = { 
        "*..........", 
        "**........*", 
        "...........", 
        "...*.......", 
        "*........*.", 
        "..........*"    
        }; 
    int rows = sizeof(map)/sizeof(map[0]); 
    int visited[rows][COLS], i, j; 

    for(i=0; i<rows; ++i){ 
     for(j=0; j<COLS; ++j) visited[i][j] = 0; 
    } 

    printf("No. of islands = %d\n", countIslands(map, visited, rows)); 


    return 0; 
} 

Si prega di suggerire una logica migliore per questo problema
anche, suggerimenti per migliorare la mia soluzione è accolto favorevolmente.

Answer 1

Penso che la confusione qui sia che il tuo algoritmo effettivamente funziona in tempo lineare, non in tempo quadratico.

Quando si utilizza la notazione O grande, n indica la dimensione di input. Il tuo input qui è non solo r o solo c, ma piuttosto, r * c, in quanto è una griglia di nodi. Il tuo algoritmo funziona in O(r * c), come hai detto nella tua domanda ... quindi il tuo algoritmo funziona in O(n) che è tempo lineare.

Mi sembra che qualsiasi algoritmo che risolve questo problema dovrà leggere ogni cella di input una volta nel peggiore dei casi. Quindi il miglior tempo di funzionamento che puoi sperare è O(n). Dato che il tuo algoritmo funziona con O(n), non puoi avere alcun algoritmo che esegua un ordine più veloce, nel peggiore dei casi, dell'algoritmo che hai proposto.

Posso pensare a qualche trucco intelligente. Ad esempio, se hai un blocco di * s, in alcuni casi puoi controllare solo le diagonali.Cioè, se si dispone di

...... 
.****. 
.****. 
.****. 
.****. 
...... 

non importa se si leggono solo queste cellule:

...... 
.*.*.. 
..*.*. 
.*.*.. 
..*.*. 
...... 

meno che, per esempio, di avere qualcosa in basso a sinistra-la maggior parte angolo, nel qual caso avresti bisogno di leggere quello in basso a sinistra *. Quindi forse in certi casi il tuo algoritmo può essere eseguito più rapidamente, ma nel peggiore dei casi (che è quello che misure O), dovrà essere O(n).

MODIFICA: anche nel caso in cui si legge solo metà dei nodi, il tempo di esecuzione è O(n/2) che è ancora dello stesso ordine (O(n)).

Answer 2

Questo è altamente correlato a connected component labeling. Il numero di componenti connessi è solo un sottoprodotto dell'etichettatura. L'algoritmo descritto nell'articolo wikipedia collegato funziona in tempo lineare.

Answer 3

1. Creare un grafico non orientato, in cui ogni nodo dell'isola si connette ai suoi nodi dell'isola neighboor.

2. Mentre ci sono i nodi non visitati:

   • scegliere un nodo non visitato, fare un attraversamento in profondità e segnare ogni nodo visitato, aumentare number_of_islands.

3. Fatto.

Entrambi (1) e (2) richiedono O (n).

Answer 4

Senza alcuna conoscenza apriori sulla natura delle isole, l'algoritmo non può essere reso più efficiente di O (n) nel tempo, tuttavia è possibile migliorare il tuo algo in termini di memoria. L'array visitato è semplicemente ridondante. Ecco un breve tentativo (pardon l'utilizzo di artihmetics ASCII - non così leggibili, ma più veloce di codice)

#include <stdio.h> 
#define COLS 12 


int main() 
{ 
    char map[][COLS] = { 
      "*..........", 
      "**........*", 
      "...........", 
      "...*.......", 
      "*........*.", 
      "..........*"    
      }; 
    int rows = sizeof(map)/sizeof(map[0]); 
    int i, j; 

    int main_count = 0; 

    if(map[0][0] == '*') { 
     main_count++; 
    } 
    for(j=0; j<COLS-1; j++) { 
     if((map[0][j]-map[0][j+1])==4) { 
      main_count++; 
     } 
    } 

    for(i=1; i<rows; ++i){ 
     if(map[i][0] == '*' && (map[i][0]-map[i-1][0]-map[i-1][1])==-50) { 
      main_count++; 
     } 
     for(j=0; j<COLS-1; j++) { 
      if((map[i][j]-map[i][j+1])==4) { 
       if(j==COLS-2 && (map[i][j+1]-map[i-1][j]-map[i-1][j+1])==-50) { 
        main_count++; 
       } 
       if(j!=COLS-2 && (map[i][j+1]-map[i-1][j]-map[i-1][j+1])-map[i-1][j+1]==-96) { 
        main_count++; 
       } 
      } 
     } 
    } 

    printf("Number of islands: %d\n", main_count); 

    return 0; 
} 

Answer 5

Asintoticamente vostro approccio è il migliore O (n).

Tuttavia, ho notato un paio di cose:

Primo:

all'interno della funzione markVisited di controllare un cellule vicini nell'ordine:

down, right, up, left, down-right, up-left, up-right, down-left 

Un ordine migliore sarebbe :

left, right, up-left, up, up-right, down-left, down, down-right 

Ciò funzionerà meglio nella cache poiché inizia leggendo i valori direttamente accanto alla posizione corrente e in sequenza in una data riga.

(notare che iniziare con le diagonali segnerà visitato in un numero maggiore di posizioni, ma dal momento che controllare se una cella è stata visitata è solo l'ultima verifica che non salverebbe in qualsiasi momento).

In secondo luogo:

Nel caso peggiore di un'immagine satellitare che contiene solo paese, l'algoritmo si recherà in visita ogni cella più volte, (qualcosa come una volta per ogni vicino la cella ha).

Ciò significa che si eseguono circa otto volte più accessi di array del necessario.

Credo che sia possibile risolvere questo problema con un passaggio più o meno lineare sui dati.

Attualmente sto pensando ad un approccio, se funziona aggiungo il codice come una modifica.