Lámpák
Egy $N\times M$-es téglalap alakú téren
$K$ lámpát helyeztek el. Mindegyiknek ismerjük a helyét. Mindegyik lámpa azt a $H\times H$-s ($H$ páratlan) négyzet alakú területet világítja be, amely átlóinak metszéspontjában áll a lámpa. A világos területek éjszaka is biztonságosak, a sötéteken azonban tanácsosabb nem járni.
Feladat
Írj programot, amely megadja, hogy mekkora a téren sötétben maradt terület (a mezők száma), valamint hogy hogyan menjünk át a tér bal felső sarkából a jobb alsó sarkába a legbiztonságosabban úgy, hogy minden pozícióról a 4 oldalszomszédjára léphetünk, átlósan pedig nem léphetünk.
Bemenet
A LAMPAK.IN szöveges állomány első sorában a tér sorai
$N$ $(1\le N\le 100)$ és oszlopai
$M$ száma $(1\le M\le 100)$, valamint a lámpák
$K$ száma $(0\le K\le 1000)$ és az általuk bevilágított négyzet oldalhossza ($1\le H\le 100$, $H$ páratlan) van.
A következő $K$ sor mindegyike egy lámpa helyét tartalmazza, egy számpárt egy szóközzel elválasztva: közülük az első egy lámpát tartalmazó mező sorindexe, a második pedig az oszlopindexe. A sorokat felülről-lefelé, az oszlopokat balról-jobbra sorszámozzuk.
Kimenet
A LAMPAK.OUT szöveges állomány első sorába a sötétben maradt mezők számát kell írni. A második sorba azon sötét mezők száma kerüljön, ahányon minimálisan át kell menni, ha a tér bal felső sarkából a jobb alsó sarkába szeretnénk eljutni.
Példa
| LAMPAK.IN | LAMPAK.OUT |
8 10 3 5
3 3
7 3
3 9 |
20
4
|
Tesztadatok
