Dominófedés
Feladat
Adott egy $n \times 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 \times 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.
Bemenet
A dom.in állomány első sora $n$ és $m$ értékét tartalmazza. $(1 \le n,m \le 100)$ A tábla mezőit balról jobbra, felülről lefelé számozzuk meg, 1-től $n\cdot m$-ig.
Az input második sora az elválasztó vonalak $l$ számát adja meg.
$(0\le l\le 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 $\frac{n\cdot 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élda
| dom.in | dom.out |
| 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 |
Tesztadatok
Példák
Az ábrákat Mészáros Balázs programja készítette.
