20. Had poskládaný v mřížce

Vstupem programu jsou tři dvojice celých čísel. První dvojice udává rozměry mřížky, druhá začátek, třetí konec hada.

Výstupem programu je seznam dvojic celých čísel. Každá dvojice udává postupně souřadnice jednoho dílku hada (včetně jeho začátku a konce). Had musí zakrývat právě celou mřížku a jeho začátek a konec musí být přesně na zadaných souřadnicích ze vstupu. Had nesmí křížit sám sebe a každé dva po sobě jdoucí dílky musejí sousedět vodorovně nebo svisle.

U vstupu je vždy zaručené, že řešení existuje. To mimo jiné znamená, že rozměry mřížky jsou kladné, souřadnice začátku a konce se nepřekrývají, jsou nezáporné a menší než příslušný rozměr mřížky.