Candale Silviu (silviu) 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:
03 111 33 110 33 110 | 040 444 040 |
| Circuitele pot să se scurtcircuiteze. | Circuitul nu are exact două capete. |
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ă.
Date de intrare
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.
Date de ieșire
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.
Restricții și precizări
1 <= N, M <= 1000pentru toate testele.1 <= N * M <= 2500pentru 20% din teste.1 <= N * M <= 10000pentru 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 (legătură 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 primește 100% din punctaj.
Exemplul 1
mz.in
8 6 122100 111100 000000 000011 222221 000011 000000 333000
mz.out
5 11 1221x0 1111x0 000xx0 xxxx11 222221 000011 000000 333000
Exemplul 2
mz.in
4 20 00000000000010000000 00000000000010000000 00000000000100000000 00000000001000000000
mz.out
3 3 00000000000x10000000 0000000000xx10000000 0000000000x100000000 00000000001000000000
Exemplul 3
mz.in
8 25 0000000000000000000000000 0000001110001010011000000 0000010001110101100100000 0000001000000100001000000 0000110000000000000100000 2111000011000000000010000 0001000000000010000012000 0001000000000000000000100
mz.out
20 8 00000xxxxxxx0000000000000 0000xx11100x1010011000000 0000x10001110101100100000 000xx01000000100001000000 0xxx110000000000000100000 2111000011000000000010000 0001000000000010000012000 0001000000000000000000100