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.