Fişierul intrare/ieşire:	mz.in, mz.out	Sursă	Grigore Moisil 2016, Clasa a 10-a
Autor	Petru Trimbitas	Adăugată de	Grigore Moisil •grigore.moisil
Timp execuţie pe test	0.5 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Marele Zgomot

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:

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

• 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.

Exemplu

Cum se trimit solutii?