Egy nehéz kutatás után Anton úgy döntött, hogy kikapcsolódik a vidéki házában. Gyönyörű kertje van sok különböző virággal. De, ó ne, megérkezésekor jelentős számú lyukat látott a földön. Ez egy vakond!
Most, egy ásóval felfegyverkezve, Anton várni fogja a vakondot. A vakond bármelyik lyukból előbukkanhat. Anton olyan pozíciót szeretne választani, hogy a legrosszabb esetben a lehető minimális idő alatt fussa le a vakondot.
A kertet egy $$$n \times m$$$ mátrixként lehet reprezentálni, ahol $$$n$$$ a sorok száma, és $$$m$$$ az oszlopok száma. A sorokat felülről lefelé, $$$1$$$-től $$$n$$$-ig számozzuk. Az oszlopokat balról jobbra, $$$1$$$-től $$$m$$$-ig számozzuk. Így a $$$(1;1)$$$ indexű cella a bal felső sarokban található.
A kert minden cellája, $$$a_{i, j}$$$, leírja a cella állapotát:
Anton tudja, hogy a lyukak száma nem haladja meg a $$$100$$$-at.
Mint olyan, aki sok időt fektetett ezekbe a virágokba, a szíve nem bírja elviselni, hogy letapossa azokat. Ezért olyan utat kell találnia, amely nem halad át rajtuk.
Bármikor Anton át tud menni a $$$(x, y)$$$ pozícióból az alábbi pozíciók egyikére: $$$(x-1,y)$$$, $$$(x+1,y)$$$, $$$(x,y-1)$$$, $$$(x,y+1)$$$, feltéve, hogy az új pozíció nem tartalmaz virágokat, és a kertben van.
Keressük meg az összes olyan pozíciót ($$$x;y$$$), ahonnan Anton a legrosszabb esetben a lehető legkevesebb idő alatt fog futni a vakondhoz.
Az első sor két egész számot tartalmaz, $$$n$$$, $$$m$$$ ($$$1 \le n \cdot m \le 2 \cdot 10^5$$$) — a kert hosszát és szélességét.
A következő $$$n$$$ sor mindegyike $$$m$$$ karaktert tartalmaz — a kert leírása.
Biztosított, hogy minden olyan cellából, amely nem tartalmaz virágokat, elérhető másik olyan cella, amely nem tartalmaz virágokat, a cellákon keresztüli mozgással, amelyek nem tartalmaznak virágokat.
Biztosított, hogy legalább egy lyuk van, és a lyukak száma a kertben nem haladja meg a $$$100$$$-at.
Az első sorban egyetlen egész számot kell kiírni, $$$x$$$ ($$$1 \leq x \leq n \cdot m$$$) — az optimális pozíciók száma.
Minden következő $$$x$$$ sorban ki kell írni az optimális pozíciókat ($$$x;y$$$) a vakondra várásra ($$$1 \le x \le n$$$, $$$1 \le y \le m$$$).
A pozíciókat bármilyen sorrendben ki lehet írni.
Legyen $$$k$$$ a lyukak száma a kertben.
3 4HF.F..HFFF.F
2 2 1 2 2
4 9......FFH.F..FHFF.HF........FHF..FFF
2 1 6 3 4
![]() |