Dominófedés (Megoldás)
Címkék > Feladat

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 \leq n, m \leq 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 \leq l \leq 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

dom_test.zip

Példák

Az ábrákat Mészáros Balázs programja készítette.