Fişierul intrare/ieşire:mz.in, mz.outSursăGrigore Moisil 2016, Clasa a 10-a
AutorPetru TrimbitasAdăugată degrigore.moisilGrigore Moisil grigore.moisil
Timp execuţie pe test1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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:

03111
33110
33110
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

  • 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

mz.inmz.out
8 6
122100
111100
000000
000011
222221
000011
000000
333000
5
11
1221×0
1111×0
000xx0
xxxx11
222221
000011
000000
333000
4 20
00000000000010000000
00000000000010000000
00000000000100000000
00000000001000000000
3
3
00000000000×10000000
0000000000xx10000000
0000000000×100000000
00000000001000000000
8 25
0000000000000000000000000
0000001110001010011000000
0000010001110101100100000
0000001000000100001000000
0000110000000000000100000
2111000011000000000010000
0001000000000010000012000
0001000000000000000000100
20
8
00000xxxxxxx0000000000000
0000xx11100×1010011000000
0000×10001110101100100000
000xx01000000100001000000
0xxx110000000000000100000
2111000011000000000010000
0001000000000010000012000
0001000000000000000000100
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?