Programozás‎ > ‎Feladatok‎ > ‎

Dominófedés

Adott egy n×m-es tábla, amelyre be van rajzolva néhány vonal. A berajzolt vonalak mindig két szomszédos mezőt választanak el. Le kell fedni a táblát 2×1-es dominókkal úgy, hogy a berajzolt vonalak nem haladhatnak keresztül dominón. Feltehetjük, hogy minden input esetén van helyes megoldás. 

     

Feladat

Írjunk programot, ami megad egy helyes dominófedést!

Bemenet

A dom.in állomány első sora n és m értékét tartalmazza. (1<=n, m<=100) A tábla mezőit balról jobbra, felülről lefelé számozzuk meg, 1-től n⋅m-ig. Az input második sora az elválasztó vonalak l számát adja meg. (0<=l<=120) Ezután l darab sorban p,q párok következnek, ahol az i-dik vonal a p és q mezőket választja el egymástól.

Kimenet

A dom.out állomány (n⋅m)/2 sora egy-egy számpárt tartalmaz. Minden sor egy dominó által lefedett két mező sorszámát adja meg. Ha több megoldás is lehetséges, akkor bármelyiket megadhatjuk.

Példák

Bemenet  Kimenet
4 5
9
8 7
13 14
14 19
6 7
12 7
4 9
12 13
14 9
9 10
3 4
1 6
2 7
8 9
5 10
14 15
11 16
12 17
13 18
19 20


A következő ábrák Mészáros Balázs programjával készültek:

    

 

Tesztadatok

Címkék

A feladat forrása: ACM ???
Algoritmusok: backtrack, visszalépéses keresés

megoldás