[c++] strano gioco... non riesco a trovare una soluzione

[mistergks]

Ho trovato un esercizio un pò complicato per me!
TRACCIA (C'è anche un disegno di esempio...lo allego come pdf)

Si consideri il seguente rompicapo illustrato dalle figure nell allegato (che riportano, rispettivamente, una possibile istanza del gioco e la sua soluzione). Si ha una griglia quadrata NxN che rappresenta la pianta della city di una moderna città. In ogni casella è presente un edificio con un certo numero di piani; in ciascuna riga e colonna gli edifici sono tutti di altezza diversa: ad esempio, in una griglia 4x4 gli edifici in ogni riga o colonna sono di 10, 20, 30 e 40 piani (1-2-3-4, per semplicità); in una griglia 5x5 ci sono anche 50 piani (5, per semplicità); e così via. I numeri nelle caselle sui bordi grigi indicano quante costruzioni può vedere un osservatore da quella casella lungo la stessa riga o colonna. Ad esempio, nello schema riportato in figura, il “2” posizionato sul bordo sinistro della riga evidenziata, indica che un osservatore in quella posizione, guardando da sinistra verso destra, vedrebbe esattamente due grattacieli; il “3” a destra della stessa riga indica che un osservatore che guardasse la riga da destra verso sinistra ne vedrebbe esattamente tre. Infatti, guardando la corrispondente riga nella soluzione, abbiamo da sinistra a destra “3-4-2-1”: quindi, guardando da sinistra verso destra si vedono solo gli edifici di 30 e 40 piani (3-4), che nascondono quelli più bassi (2-1); guardando da destra a sinistra, abbiamo “1-2-4-3”, e gli edifici visibili sono quelli di 10, 20 e 40 piani (1-2-4), mentre quello di 30 piani (3) è nascosto alla vista da quello più alto (4). Naturalmente, gli indizi valgono nello stesso modo per ogni riga, e similmente per ogni colonna.

Si scriva in C++ una funzione che, ricevuta in input una soluzione candidata, restituisca “true” se la soluzione è ammissibile (cioè rispetta tutti gli indizi di riga e colonna), “false” altrimenti. 
SUGGERIMENTO: La griglia (corrispondente alla parte “bianca” in figura) può essere rappresentata da una matrice di interi senza segno di dimensione NxN; gli indizi per righe e colonna (corrispondenti alla parte “grigia” in figura), invece, possono essere rappresentati da 2 matrici di interi senza segno:  int indiziRiga[N][2], indiziColonna[N][2]. Ad esempio, nella matrice “indiziRiga”, per ogni riga “i”, l’elemento “indiziRiga[i][1]” potrebbe riportare l’indizio da sinistra a destra, e l’elemento “indiziRiga[i][2]” potrebbe riportare l’indizio da destra a sinistra; similmente si può intendere per gli indizi di colonna.

Oltre al fatto che ci abbia messo una vita per capire quello che chiede.... non sono riuscito a scrivere nulla!! Ho sempre scritto il mio codice nei post...ma questa volta non so da dove iniziare.
Infatti ho deciso di postare questa mia richiesta di aiuto non per chiedere la soluzione già pronta...ma per cercare qualcuno che mi aiuti a ragionare... e permettermi di iniziare a scrivere questa funzione

N.B.: Questa funzione non deve risolvere il gioco...ma deve solo verificare che una data soluzione sia corretta!

Allora... io avrei pensato a questa soluzione:
faccio due matrici: indiziRiga e indiziColonna dove vengono messi gli indizi
poi mi scansiono queste due matrici (non insieme ovviamente)e controllo che le condizioni siano verificate. cioè ad esempio:
se scansiono indiziRiga[0][0] trovo il numero 3... quindi in quella riga della matrice alla posizione 2 deve esserci un numero=dimensione matrice (in questo caso 4...perchè la matrice è 4x4)...

[banryu79]

Riposto il testo nei tag QUOTE, a favore della leggibilità (scrollare righe lunghe 1 metro non è il massimo):

Si consideri il seguente rompicapo illustrato dalle figure nell allegato (che riportano, rispettivamente, una possibile istanza del gioco e la sua soluzione). Si ha una griglia quadrata NxN che rappresenta la pianta della city di una moderna città.
In ogni casella è presente un edificio con un certo numero di piani; in ciascuna riga e colonna gli edifici sono tutti di altezza diversa: ad esempio, in una griglia 4x4 gli edifici in ogni riga o colonna sono di 10, 20, 30 e 40 piani (1-2-3-4, per semplicità); in una griglia 5x5 ci sono anche 50 piani (5, per semplicità); e così via.
I numeri nelle caselle sui bordi grigi indicano quante costruzioni può vedere un osservatore da quella casella lungo la stessa riga o colonna. Ad esempio, nello schema riportato in figura, il “2” posizionato sul bordo sinistro della riga evidenziata, indica che un osservatore in quella posizione, guardando da sinistra verso destra, vedrebbe esattamente due grattacieli; il “3” a destra della stessa riga indica che un osservatore che guardasse la riga da destra verso sinistra ne vedrebbe esattamente tre.
Infatti, guardando la corrispondente riga nella soluzione, abbiamo da sinistra a destra “3-4-2-1”: quindi, guardando da sinistra verso destra si vedono solo gli edifici di 30 e 40 piani (3-4), che nascondono quelli più bassi (2-1); guardando da destra a sinistra, abbiamo “1-2-4-3”, e gli edifici visibili sono quelli di 10, 20 e 40 piani (1-2-4), mentre quello di 30 piani (3) è nascosto alla vista da quello più alto (4).
Naturalmente, gli indizi valgono nello stesso modo per ogni riga, e similmente per ogni colonna.

Si scriva in C++ una funzione che, ricevuta in input una soluzione candidata, restituisca “true” se la soluzione è ammissibile (cioè rispetta tutti gli indizi di riga e colonna), “false” altrimenti.

SUGGERIMENTO: La griglia (corrispondente alla parte “bianca” in figura) può essere rappresentata da una matrice di interi senza segno di dimensione NxN; gli indizi per righe e colonna (corrispondenti alla parte “grigia” in figura), invece, possono essere rappresentati da 2 matrici di interi senza segno:
int indiziRiga[N][2], indiziColonna[N][2]. Ad esempio, nella matrice “indiziRiga”, per ogni riga “i”, l’elemento “indiziRiga[i][1]” potrebbe riportare l’indizio da sinistra a destra, e l’elemento “indiziRiga[i][2]” potrebbe riportare l’indizio da destra a sinistra; similmente si può intendere per gli indizi di colonna.

La soluzione che hai proposto va bene, in pratica controlli che tutte le condizioni stabilite dalle due righe e due colonne di indizi.

[mistergks]

Originariamente inviato da banryu79

Riposto il testo nei tag QUOTE, a favore della leggibilità (scrollare righe lunghe 1 metro non è il massimo):


La soluzione che hai proposto va bene, in pratica controlli che tutte le condizioni stabilite dalle due righe e due colonne di indizi.

Ora che ci penso c'è un problema: cosi facendo non posso stabilire se prima del 4 ci sono ad esempio 1,2,3 o 1,3,2... Nell ultimo caso il palazzo 2 sarebbe oscurato dal 3 scansionando da sinistra verso destra! Quindi non puo andare

Inviato dal mio GT-I9003 usando Tapatalk

[banryu79]

Non ho capito: io non vedo nessun problema.
La logica è questa:

per ogni indizio-riga
    poni palazzi-visti a 0
    poni altezza a 0
    per ogni casella in indizio-riga
        se valore casella > valore altezza
        allora poni valore altezza a valore casella e incrementa palazzi-visti di 1
    se valore palazzi-visti != valore indizio-riga
    allora esci (soluzione non valida)
esci (soluzione valida)

Devi fare il controllo per entrambe le righe (destra/sinistra) e colonne (sopra/sotto). Basta che un solo controllo fallisca e la soluzione è errata; viceversa, se tutti i controlli passano la soluzione è corretta.

La logica del controllo resta sempre la stessa, ciò che cambia per ogni riga e colonna sono gli elmenti da controllare e l'ordine in cui vanno scanditi (bisogna rispettare l'ordine con cui si presentano all'osservatore).

[mistergks]

Originariamente inviato da banryu79

Non ho capito: io non vedo nessun problema.
La logica è questa:

per ogni indizio-riga
    poni palazzi-visti a 0
    poni altezza a 0
    per ogni casella in indizio-riga
        se valore casella > valore altezza
        allora poni valore altezza a valore casella e incrementa palazzi-visti di 1
    se valore palazzi-visti != valore indizio-riga
    allora esci (soluzione non valida)
esci (soluzione valida)

Devi fare il controllo per entrambe le righe (destra/sinistra) e colonne (sopra/sotto). Basta che un solo controllo fallisca e la soluzione è errata; viceversa, se tutti i controlli passano la soluzione è corretta.

La logica del controllo resta sempre la stessa, ciò che cambia per ogni riga e colonna sono gli elmenti da controllare e l'ordine in cui vanno scanditi (bisogna rispettare l'ordine con cui si presentano all'osservatore).

Grazie...sei riuscito a farmi almeno scrivere qualcosa.. anche se è sbagliata..è un passo avanti
Per ora ho fatto solo l'osservazione da sinistra verso destra dato che poi la logica è uguale e cambia solo il metodo di accesso..
Però ahimè...non funziona...pur compilando correttamente.

#include <iostream>
using namespace std;

const int n=4;

bool verifica(int M[][n], int n, int indiziRiga[2][n]);


int main(){
    
    int M[n][n]={{1,3,4,2},
                 {3,4,2,1},
                 {4,2,1,3},
                 {2,1,3,4}};
                 
    int indiziRiga[2][n]={{3,2,1,3},
                          {2,3,2,1}};
    
    int indiziColonna[2][n]={{3,2,1,3},
                             {2,3,2,1}};
    
        
        if(verifica(M,n,indiziRiga))
            cout<<"ok"<<endl;
        else cout<<"no"<<endl;
    
    
    
system("pause");
return 0;
}

bool verifica(int M[][n], int n, int indiziRiga[2][n]){
     
     int palazzivisti=0, altezza=0;
     
         for(int i=0; i<n; i++){
                 for(int j=0; j<n; j++){
                            if(M[i][j] > altezza){                       
                                                altezza=M[i][j];                         
                                                palazzivisti++;  }
                 if(palazzivisti > indiziRiga[0][i])
                 return false;
                            }
}

return true;

}

[mistergks]

up

Inviato dal mio GT-I9003 usando Tapatalk