Problemino....battaglia navale

[Mezzetti0903]

Chi di voi mi può scrivere uno pseudocodice per questo problema?

Scrivere una procedura int navi(char **a, int n) che data una matrice di caratteri di dimensione
n×n contenente soltanto valori 0 e 1 restituisca il numero di sottomatrici contenenti solo il valore 1
massimali (una sottomatrice di 1 `e massimale se non esiste un’altra sottomatrice di 1 che la contiene).
Si assuma che due sottomatrici massimali distinte non siano adiacenti. [Spiegazione: la matrice
rappresenta uno schema di “battaglia navale” e si deve contare quante navi sono presenti; le navi
sono rettangoli di 1 di qualsiasi dimensione e si posso toccare solo in un vertice].
Scrivere poi una procedura int verifica(char **a, int n) che restituisce 0 se e solo se la matrice
viola il vincolo sopra descritto cio`e contiene due sottomatrici di 1 massimali adiacenti.

E' nel testo di un compito della mia ragazza e ci ho pensato un po' e non mi viene nè' un idea banale per risolvere...nè (andando nello scrivere un sacco di codice) un idea corretta ma macchinosa.
Voi che dite?

Grazie!

[Mezzetti0903]

up...

[andbin]

Guarda, ammettendo che le navi non possano essere adiacenti in alcun modo (cioè che non si tocchino tra di loro) e che una nave sia composta da almeno 2 celle, dovrebbe essere sufficiente fare una scansione prima in orizzontale e poi in verticale della tabella.

[Mezzetti0903]

Cioè? cosa intendi?

non so se con la tua idea c'entri qualcosa ma qua le navi possono essere anche 2*3 3*3...e non solo rettangolari di lato uno....(lo dico perchè secondo me l'esempio delle navi è fuorviante)

[andbin]

Originariamente inviato da Mezzetti0903

non so se con la tua idea c'entri qualcosa ma qua le navi possono essere anche 2*3 3*3...e non solo rettangolari di lato uno....(lo dico perchè secondo me l'esempio delle navi è fuorviante)

Io intendevo blocchi di dimensione 1xN o Nx1 (il classico del battaglia navale).

Comunque lasciamo stare le navi ..... parliamo di sottomatrici. A te interessa solo contare il numero di sottomatrici, vero? Se come dici i blocchi possono occupare più righe/colonne, la cosa è un pochino più complessa.

Però mi è venuta in mente adesso una possibile soluzione, che però è "invasiva" per quanto riguarda l'uso della tabella.

Mi spiego meglio: si scansiona tutta la tabella, si fa in pratica il classico doppio ciclo for per righe e colonne. Ogni volta che viene trovato il valore 1 si fa la seguente cosa: si incrementa il contatore delle sottomatrici e poi si azzera la sottomatrice. Cercando nelle varie direzioni altri 1 adiacenti, li si azzera.
Finito l'azzeramento, si continua nella scansione della matrice. Chiaramente avendo tolto la sottomatrice, non salterà più fuori in colonne/righe seguenti.

Se non fosse chiaro, spiego meglio.

[Mezzetti0903]

Ad una soluzione di questo tipo ci ero arrivato anche io ma non l'avevo postata per lasciare il problema aperto e perchè sostanzialmente è proprio brutta.

static int numeroNavi(int x, int y)
        {
            int xInizio=x,xFine=x,yInizio=y,yFine=y;
            /*Finchè cresce
            /*Posso accrescerla in altezza o in lunghezza o tutti e due*/
            /*ACCRESCO IN ALTEZZA*/
            while (yInizio > 0 && matr[x, yInizio-1] == 1)
            {
                yInizio--;
            }
            while(yFine < matr.GetLength(1)-1 && matr[x,yFine+1] == 1){
                yFine++;
            }
            /*Accresco in lunghezza*/
            while (xInizio > 0 && matr[xInizio-1, y] == 1)
            {
                xInizio--;
            }
            while (xFine < matr.GetLength(0) - 1 && matr[xFine+1, y] == 1)
            {
                xFine++;
            }
/*CONTROLLI DA FARE E NON PRESENTI NEL CODICE:*/
            /* Adesso che non posso accrescere tutto quello che è dentro deve essere pieno di uno altrimenti lancio eccezione*/
            /* Tutta la corona esterna della matrice deve essere di 0, tranne nei vertici altrimenti lancio un eccezione*/

            /*Tolgo la sottomatrice trovata*/
            for (int i = xInizio; i <= xFine; i++)
                for (int z = yInizio; z <= yFine; z++)
                    matr[i, z] = 0;

            
            int nx,ny;
            if (trovaUno(out nx, out ny))
                return numeroNavi(nx, ny) + 1;
            else
                return 1;

        }
       static bool trovaUno(out int x, out int y){
           for(int i = 0; i < matr.GetLength(0); i++)
               for(int z = 0; z < matr.GetLength(1); z++)
                   if (matr[i, z] == 1)
                   {
                       x = i;
                       y = z;
                       return true;
                   }
           x = y = 0;
           return false;

       }

i motivi per cui non mi piace sono :
1) è invasiva sulla tabella
2) trovaUno non tiene conto delle matrici già trovate ed azzerate e quindi non è molto efficente.

Volevo trovare una soluzione più carina...almeno per risolvere il problemino 2.

Altre idee?!

Comunque grazie di avermi risposto...degli altri nessuno ha provato.

[andbin]

Originariamente inviato da Mezzetti0903

Ad una soluzione di questo tipo ci ero arrivato anche io ma non l'avevo postata per lasciare il problema aperto e perchè sostanzialmente è proprio brutta.

Guarda, ho provato a scrivere del codice, tanto per cimentarmi anche io con questo problema. La tua soluzione che hai postato adesso è praticamente uguale come concetto a quella che avevo detto io.
Salvo il fatto che io per l'azzeramento della sottomatrice ho usato una funzione ricorsiva che richiama sé stessa per spostarsi nelle possibili (max 4) direzioni. Che è poi nient'altro che l'algoritmo del "flood-fill" usato in grafica e che permette di trattare aree anche di forma irregolare.