vicini collegati in un array di Java 2D

Question

Sto progettando un motore per un gioco che ha una matrice 2D come questo:

0,1,1,2,0 
0,1,2,1,1 
1,0,1,0,2 
2,1,2,0,0 
2,0,1,0,0 

Sono bloccato al "game over" condizione in quanto deve controllare se 1 o 2 sono collegati. Dovrebbe dichiarare il giocatore con 1 del vincitore e restituire questo:

1 1 
1 1 1 
1 1 
1 
    1 
    1 

Ho provato con la ricorsione controllando ogni posizione nella matrice e controllando i suoi vicini in tutte le 8 direzioni, ma il metodo sono voluti 45 secondi per l'esecuzione che è inefficiente.

Qualcuno ha qualche idea? Un esempio di pseudo-codice sarebbe apprezzato (io sono uno studente lento).

Answer 1

andare avanti e fare un grafico duplicato a[n][n] con a[i][j] = 1 se i e j sono collegati.

Quindi è possibile effettuare le seguenti operazioni:

int count = 0; 

void dfs(int i) 
{ 
    int k; 
    for(k = 0; k < n; k++) 
    { 
     if(A[i][k] == 1 && !visited[k]) 
     { 
      count++; 
      visited[k] = 1; 
      dfs(k); 
     } 
    } 
} 

for(i=0; i < n;i++) 
{ 
    if(!visited[i]) 
    { 
     count=1; 
     visited[i]=1; 
     dfs(i); 
     // map i with count .. here 
    } 
} 

Quindi, una volta che avete fatto la mappatura numero di nodi in una rete con uno dei suoi nodi.

Troverete conteggio valore e se count == di total_no_of_1

Se è così allora Rete 1 è collegato .if non poi lo stesso con 2 e di conseguenza e dichiarano.

Answer 2

ecco alcuni suggerimenti:

• Se possibile, tenere traccia di quante 1 e 2 di ci sono fin dall'inizio.
• Quando si verifica se sono connessi, è possibile utilizzare una matrice boolean e un contatore, per tenere traccia di quelli già controllati e quanti di essi.
• Utilizzare la ricorsione sui vicini necessari invece di controllare ogni posizione nella matrice.

Answer 3

Questa domanda non è così semplice. Mi sembra che tu possa guardare la tua matrice come un grafico e tu cerchi di scoprire se il tuo grafico è connesso. cioè il grafico di 1s connesso ed è il grafico di 2s connesso. Qui vedi un few algorithms. Dato che stai creando il grafico puoi anche tenere traccia dei gruppi di nodi creati da un giocatore e creando un nuovo nodo, puoi verificare quanti gruppi sono connessi al nuovo nodo e unione qualunque sia connesso dal nuovo nodo (o crea un nuovo gruppo contenente il tuo nuovo nodo se non connette nulla).

btw è possibile convertire qualsiasi ricorsione in un ciclo, ma ciò dovrebbe essere necessario solo se lo stack si esaurisce.

Answer 4

Mantenere una struttura dati UnionFind dall'inizio, ogni voce rappresenta ciascuna cella. Inizialmente, eseguire un'unione su celle adiacenti con gli stessi valori. Quando un giocatore segna una cella, esegui un'unione() con le celle adiacenti se il valore è uguale al valore del giocatore. Nel Trova Unione, puoi tenere traccia del numero di celle che hanno un valore, quando quel numero è uguale al numero di volte che quel valore è stato inserito, hai un vincitore.

È anche farlo linearmente utilizzando l'algoritmo descritto here

Answer 5

Quello che vi serve è che:

Connected_component_labeling

Questo dà una pseudo codice,

Speranza che aiuta