Prázdny
Prázdny

Úloha č. 5

Musíte sa prihlásiť

ZADANIE

 

Ostrovy a mosty

Dostaneš mapu ostrovov vo forme matice, kde 1 sú pevnina a 0 sú voda.
Tvojou úlohou je vypočítať, koľko materiálu je potrebné na spojenie všetkých ostrovov mostami. Ostrov je definovaný ako oblasť pozemných buniek spojených buď vertikálne alebo horizontálne.
Most možno postaviť z 1, 2 alebo 3 po sebe nasledujúcich buniek. Jedna bunka sa považuje za jednu jednotku materiálu. Mosty sa stavajú len v horizontálnom alebo vertikálnom smere.
Cieľom je spojiť všetky ostrovy. Mosty sa môžu krížiť, avšak bunka obsahujúca 2 mosty súčasne sa považuje za 2 materiálové jednotky.

 

Vstup

Vstup začína počtom testovacích prípadov T (0 ≤ T ≤ 100). Každý testovací prípad začína riadkom obsahujúcim dve celé čísla N a M (1 ≤ N ≤ 100, 1 ≤ M ≤ 100), kde N je počet riadkov a M je počet stĺpcov v matici. Potom nasleduje N riadkov, z ktorých každý obsahuje M celých čísel z množiny {0, 1}.

 

Výstup

Pre každý testovací prípad vytlač riadok obsahujúci množstvo materiálu potrebného na stavbu mostov, ktoré sú schopné spojiť všetky ostrovy. Ak sa ostrovy nedajú spojiť, vytlač -1.

 

Do políčka s odpoveďou zadaj riešenie a zdrojový kód tvojho programu.

 

Príklad:

Input:

3

6 3

000

010

000

000

010

000

6 5

00000

01001

01101

00001

01001

01000

3 5

01100

10100

01001

 

Output

2
2
4

 

 

 

Vysvetlenie:
Priklad 1:
Sú 2 ostrovy A a B, ktoré môžu byť prepojené 1 mostom s dĺžkou 2.

 A

 |

 |

 B

 

 

Príklad 2:

Sú 3 ostrovy AB a C, ktoré môžu byť prepojené 2 mostami s dĺžkou 1.

   A    B

   AA-B

   |     B

   C   B

   C

 

Príklad 3

Sú 4 ostrovy ABC a D, ktoré môžu byť spojené 2 krížiacimi sa mostami s dĺžkou 1 a jedným mostom s dĺžkou 2.

AA

B+A

 C--D

 

Súbor na stiahnutie

 

ODPOVEĎ na súťažnú úlohu sa dozviete TU