Blokiranje
Dat je lavirint oblika pravougaonika, dimenzija NxM. Ulaz u lavirint je na polju (1,1) a izlaz na polju (N,M). Polje (1,1) je gornji levi ugao lavirinta, a (N,M) donji desni ugao. Neka polja u lavirintu su zidovi, i na njih se ne moze stati, sva ostala polja su slobodna. Polja (1,1) i (N,M) ce uvek biti slobodna. Kroz lavirint se moze kretati u 4 smera (gore, dole, levo, desno).
Da li je moguce postaviti zid na tacno jedno slobodno polje u lavirintu, tako da ne postoji izlaz iz lavirinta (tj. da ne postoji put od polja (1,1) do (N,M))? Zid se ne sme postaviti na polja (1,1) i (N,M).
Ispisati koordinate svih polja koja zadovoljavaju ovaj uslov.
Primeri ce biti takvi da ce K, odnosno broj polja koji su resenje zadatka, uvek biti manji od 100.000
Ogranicenja:
U 20% primera ce biti: 1 <= N, M <= 35
u 50% primera ce biti: 1 <=N, M <= 200
u 100% primera ce biti: 1 <= N, M <= 1.000
Ulaz:
5 5
.#...
.#...
.#...
...#.
...#.
Izlaz:
7
2 1
3 1
3 3
3 5
4 1
4 3
4 5
Ulaz:
2 5
..#..
..#..
Izlaz:
6
1 2
1 4
1 5
2 1
2 2
2 4
Ulaz:
1 2
..
Izlaz:
0
Objasnjenje 1. primera:
Ukoliko postavimo zid npr. na polje (3,5) lavirint ce izgledati ovako:
.#...
.#...
.#..#
...#.
...#.Pa nece postojati put od polja (1,1) do (5,5). Isto vazi i za sva ostala polja iz izlaza.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.