Chiarimento esercizio 57 dell'eserciziario

f
fraa.dap (1280 points)
4 10 15
asked Jan 17 in Eserciziario d'esame by fraa.dap (1,280 points)
Salve, sto facendo un po' di esercizi per preparmi all'esame, non riesco a capire la traccia di questo esercizio (57).

Data una griglia NxN, se la griglia rappresenta un puzzle di grattacieli, ritorna le 4 liste Nord, Est Sud, Ovest, altrimenti ritorna 4 liste vuote

Non capisco secondo quale logica dovrei calcolare i puzzle. Dalla traccia è poco intuitivo perché c'è solo un esempio di risoluzione.

Grazie

2 Answers

I
Ionut_02 (4340 points)
3 4 18
answered Jan 17 by Ionut_02 (4,340 points)
descriverò la matrice fatta sul momento

[4,0,3]

[3,2,1]

[2,1,5]

adesso (se non mi sbaglio) dovremmo guardare i palazzi da nord verso sud e viceversa, da ovest a est e viceversa, quindi partendo da nord verso sud

Analizzerò la matrice per colonne e prendendo la prima colonna [4,3,2] analizzo l'altezza del primo cioè 4 e poi di quello dopo/dietro che è tre e di conseguenza non potrò vederlo perché è meno alto di quelli di fronte(alla dine vediamo solo 1 palazzo da nord a sud per la prima colonna)

Per la seconda colonna([0,2,1]) non possiamo vedere 1 perché ha davanti 2

Per la Terza colonna [3,1,5] vediamo il palazzo di altezza 3 perché davanti non ha nessun palazzo più alto di lui, mentre 1 ha davanti 3 e di conseguenza non si vedrà, infine abbiamo 5 e il palazzo più alto che avrà di fronte è 3 che è più basso, e di conseguenza lo possiamo vedere(da nord verso sud)
andrea.sterbini (172780 points)
514 935 1789
answered Jan 17 by andrea.sterbini (172,780 points)

Quello che devi fare è, data una matrice NxN in cui in ogni riga e colonna ci sono i valori diversi da 1 a N che indicano l'altezza dei grattacieli,
calcolare per ogni riga e colonna quanti grattacieli ci vedono da quella parte tenendo conto che un grattacielo più alto coprirà tutti i grattacieli a lui più bassi.  

numero di grattacieli visibili da sopra (nord)
2 2 2 1
v v v v
numero di grattacieli 4 '==> 1 2 3 4 <== 1 numero di grattacieli visibili da destra (est)
visibili da sinistra (ovest) 1 '==> 4 1 2 3 <== 2
2 '==> 3 4 1 2 <== 2
3 '==> 2 3 4 1 <== 2
^ ^ ^ ^
3 2 1 4
numero di grattacieli visibili da sotto (sud)