== include(page="template/taskheader" task_id="mz") ==
Poveste şi cerinţă...
Fericit că s-a calificat la ONI, XORin vrea să sărbătorească făcând cât mai mult zgomot. Deoarece e programator, acesta s-a gândit să automatizeze felul în care face zgomot.
Pentru a face zgomot el foloseşte o placă cu circuite de diverse intensităţi.
Placa poate fi reprezentată sub forma unei matrice cu $N$ linii şi $M$ coloane. Fiecare celulă din matrice are o intensitate între $0$ şi $9$ (o celulă cu intensitatea $0$ corespunde unei zone goale, fără nici un circuit).
Un circuit începe într-o celulă a matricei şi se termină în altă celulă, fiind o succesiune de celule adiacente de aceeaşi intensitate de la un capăt la celălalt al circuitului, asemenea unui drum pe matrice între cele două celule. Două celule se consideră adiacente dacă au o latură comună, deci o celulă e adiacentă cu maxim patru alte celule.
Placa a fost concepută în aşa fel încât să nu apară scurtcircuite, aşadar curentul dintr-un circuit poate merge numai într-o singură direcţie (cu alte cuvinte, fiecare celulă dintr-un circuit se învecinează cu maxim alte două celule din acelaşi circuit). Nu există circuite de aceeaşi intensitate care să se învecineze.
Zgomotul produs de un circuit este egal cu lungimea lui, adică cu numărul de celule din matrice corespunzătoare circuitului.
Exemple de circuite invalide:
|{width:80px}. 0[*3*] *111*
*33* [*11*]0
*33* [*11*]0
|{width:80px}. 0[*4*]0
*444*
0[*4*]0
|
|Circuitele pot să se scurtcircuiteze.
|Circuitul nu are exact două capete.
|
h2. Cerinţe
1) Să se afle numărul de circuite.
2) Să se afle valoarea zgomotului maxim care poate fi obţinut unind două circuite. Două circuite pot fi unite dacă se poate trage o legătură de la un capăt al unui circuit până la un capăt al celuilalt circuit, numai prin celulele libere ale matricei (de intensitate $0$). Legătura trebuie să aibă forma unui circuit. Lungimea circuitului nou creat nu se adaugă la zgomotul produs de cele doua circuite.
3) Să se afişeze placa ce conţine legătura care uneşte două circuite din care se obţine zgomotul maxim de la cerinţa 2. Dacă există mai multe variante, se poate afişa orice placă care conţine legătura validă.
h2. Date de intrare
Fişierul de intrare $mz.in$ ...
Pe prima linie a fişierului $mz.in$ se vor afla $N$ şi $M$, lungimea şi lăţimea plăcii.
Pe urmatoarele N linii se vor afla M numere care vor caracteriza intensitatea circuitului care trece prin celula respectivă. În cazul în care prin celula respectivă nu trece un circuit, în fişier se va afla caracterul 0.
h2. Date de ieşire
În fişierul de ieşire $mz.out$ ...
Prima linie a fişierului $mz.out$ va conţine pe prima linie numărul de circuite.
A doua linie va conţine lungimea maximă a unui circuit care poate fi obţinut unind două circuite.
Pe următoarele linii se va afişa matricea care conţine circuitul nou format. Fiecare celulă din legătură prin care trece circuitul va fi marcată prin caracterul $'x'$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N, M ≤ 1 000$ pentru toate testele.
* $1 ≤ N * M ≤ 2 500$ pentru 20% din teste.
* $1 ≤ N * M ≤ 10 000$ pentru 40% din teste.
* Se garantează existenţa a cel puţin 2 circuite care pot fi unite.
* Două circuite pot fi unite doar prin capetele lor (capetele legăturii dintre circuite trebuie să fie adiacente cu câte un capăt al fiecărui circuit unit).
* Două circuite nu pot fi unite decât prin zone libere (legatură se poate forma doar pe celule de intensitate 0).
* În cazul în care există mai multe soluţii la cerinţa 3, se va afişa oricare dintre ele.
* Pentru rezolvarea corectă a cerinţei (1) se primeşte $20$% din punctaj.
* Pentru rezolvarea corectă a cerinţelor (1) şi (2) se primeşte $50$% din punctaj.
* Pentru rezolvarea corectă a tuturor celor 3 cerinţe se primeste $100$% din punctaj.
h2. Exemplu
table(example). |_. mz.in |_. mz.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 8 6
122100
111100
000000
000011
222221
000011
000000
333000
| 5
11
1221x0
1111x0
000xx0
xxxx11
222221
000011
000000
333000
|
|4 20
00000000000010000000
00000000000010000000
00000000000100000000
00000000001000000000
|3
3
00000000000x10000000
0000000000xx10000000
0000000000x100000000
00000000001000000000
|
|8 25
0000000000000000000000000
0000001110001010011000000
0000010001110101100100000
0000001000000100001000000
0000110000000000000100000
2111000011000000000010000
0001000000000010000012000
0001000000000000000000100
|20
8
00000xxxxxxx0000000000000
0000xx11100x1010011000000
0000x10001110101100100000
000xx01000000100001000000
0xxx110000000000000100000
2111000011000000000010000
0001000000000010000012000
0001000000000000000000100
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="mz") ==
== include(page="template/taskfooter" task_id="mz") ==
