Skyscrapers P47245

Statement

thehtml

Skyscrapers és un solitari de la família del Sudoku. Considereu un tauler T de mida ‍n × n, on totes les files i columnes contenen una permutació de { 1, …, n }. A la dreta en veiem un exemple amb n=4. El tauler representa un mapa amb un edifici a cada casella, i T_ij és l’alçària (en la tercera dimensió) de l’edifici situat a la posició (i, j). Si ens posem al nord d’una columna j del tauler, i mirem cap al sud, veurem tots els edificis de la columna j que no estiguin tapats per algun edifici més proper a nosaltres que sigui més alt. Similarment, si ens posem al sud i mirem la columna cap al nord, si ens posem a l’oest i mirem la fila cap a l’est, i si ens posem a l’est i mirem la fila cap a l’oest.

(8,8) unit=0.65cm, linewidth=0.9

linecolor=black

-(2,2)(2,6) -(3,2)(3,6) -(4,2)(4,6) -(5,2)(5,6) -(6,2)(6,6) -(2,2)(6,2) -(2,3)(6,3) -(2,4)(6,4) -(2,5)(6,5) -(2,6)(6,6)

(2.5,5.5)4 (3.5,5.5)3 (4.5,5.5)2 (5.5,5.5)1 (2.5,4.5)2 (3.5,4.5)1 (4.5,4.5)4 (5.5,4.5)3 (2.5,3.5)1 (3.5,3.5)4 (4.5,3.5)3 (5.5,3.5)2 (2.5,2.5)3 (3.5,2.5)2 (4.5,2.5)1 (5.5,2.5)4

(2.5,6.5)1 (3.5,6.5)2 (4.5,6.5)2 (5.5,6.5)3

(2.5,1.5)2 (3.5,1.5)2 (4.5,1.5)3 (5.5,1.5)1

(1.5,5.5)1 (1.5,4.5)2 (1.5,3.5)2 (1.5,2.5)2

(6.5,5.5)4 (6.5,4.5)2 (6.5,3.5)3 (6.5,2.5)1

linecolor=red (2.5,6.5)0.4

linecolor=green (6.5,5.5)0.4

linecolor=cyan (1.5,4.5)0.4

Per exemple, l’1 marcat en vermell indica que, si mirem al sud des d’aquella posició, només veiem l’edifici més alt, d’alçària 4, el qual tapa la resta d’edificis. El 4 marcat en verd indica que, si mirem a l’oest, veiem tots els edificis. El 2 marcat en blau cel indica que, si mirem a l’est, veiem exactament dos edificis, d’alçàries 2 i 4.

La vostra tasca és reconstruir el tauler a partir dels comptadors d’edificis visibles des de les 4n posicions al voltant del tauler.

Entrada

L’entrada consisteix en diversos casos, cadascun amb una n entre 1 i 6, seguida de quatre seqüències amb n comptadors entre 1 i n, corresponents al nord, sud, oest i est en aquest ordre (d’esquerra a dreta o de dalt a baix). El primer exemple d’entrada es correspon a la figura anterior. Cada cas té almenys un tauler consistent amb els comptadors donats.

Sortida

Per a cada cas, escriviu tots els taulers consistents amb els comptadors, en ordre lexicogràfic. Per ordenar-los, suposeu que els recorreu per files de dalt a baix, i cada fila d’esquerra a dreta. Al tercer exemple d’entrada, “3512421453542311354242315” ha d’anar abans que “3521424153524311354241325”. Escriviu una línia amb 20 guions després de cada tauler.

Observació

La solució esperada és un backtracking que es pot optimitzar de moltes maneres. En funció de com d’eficient sigui el codi que envieu, el jutge us donarà una aproximació a la vostra nota màxima (60, 80 o 100 punts sobre 100). Per exemple, una solució intermèdia comprova els comptadors de cada fila completada abans de passar a omplir la següent.

Public test cases

Input

Output

4 3 2 1
2 1 4 3
1 4 3 2
3 2 1 4
--------------------
1
--------------------
3 5 1 2 4
2 1 4 5 3
5 4 2 3 1
1 3 5 4 2
4 2 3 1 5
--------------------
3 5 2 1 4
2 4 1 5 3
5 2 4 3 1
1 3 5 4 2
4 1 3 2 5
--------------------

Information

Author: Salvador Roura
Language: Catalan
Official solutions: C++
User solutions: C++