piese

Piese

h2. Date de iesire

In fisierul de iesire $piese.out$ se va scrie pe prima linie {$MIN$}, numarul minim de piese folosit. Fiecare din urmatoarele $M$ linii contine cate $N$ numere ce descriu acoperirea cu piese a tablei. Oricare piesa va avea asociat un unic numar natural de la $1$ la {$MIN$}. Astfel, al $j$-lea numar de pe linia $i+1$ ({$i$} de la $1$ la $M$, $j$ de la $1$ la {$N$}) reprezinta numarul piesei care acopera patratelul de coordonate {$(i j)$} de pe tabla.

In fisierul de iesire $piese.out$ se va scrie pe prima linie {$MIN$}, numarul minim de piese folosit. Fiecare din urmatoarele $M$ linii contine cate $N$ numere ce descriu acoperirea cu piese a tablei. Oricare piesa va avea asociat un numar natural unic de la $1$ la {$MIN$}. Astfel, al $j$-lea numar de pe linia $i+1$ ({$i$} de la $1$ la $M$, $j$ de la $1$ la {$N$}) reprezinta numarul piesei care acopera patratelul de coordonate {$(i j)$} de pe tabla. Daca sunt mai multe solutii cu numar minim de piese se poate afisa oricare.

h2. Restrictii
* $1 ≤ M, N ≤ 500$

* Punctajul pe un test nu se acorda decat daca acoperirea cu piese este corecta (este folosit un numar minim de piese de tipul celor descrise mai sus si tabla este acoperita in intregime)

h2. Exemplu
table(example). |_. piese.in |_. piese.out |

|4 3

|3 4

|6

1 1 2
1 1 3
4 5 5
6 5 5

1 1 2 4
1 1 3 3
5 6 3 3

|
h3. Explicatie
Acoperirea din exemplu corespunde figurii:

!?acoperie.bmp?

!problema/piese?acoperire.bmp!

== include(page="template/taskfooter" task_id="piese") ==

2599