blind

Fie o matrice de dimensiuni $N \times M$ care conține numai valorile $0$ și $1$. Căsuțele marcate cu $0$ sunt inaccesibile, în timp ce căsuțele marcate cu $1$ sunt accesibile.

Gimi se va afla inițial într-o căsuță marcată cu $1$ din această matrice, poziția ei nefiind însă cunoscută nouă. Lui Gimi îi putem da instrucțiuni de tipul: deplasează-te în căsuța $(x_d, y_d)$. Regulile sunt următoarele:

• Gimi se poate deplasa numai în căsuțe marcate cu $1$.
• Gimi se poate deplasa numai în căsuțe vecine cu cea în care se află. Căsuțele vecine cu $(x, y)$ sunt (cât timp sunt în matrice): $(x - 1, y)$, $(x, y + 1)$, $(x + 1, y)$ și $(x, y - 1)$.

Dacă Gimi poate respecta toate regulile, atunci acesta se va deplasa în căsuța $(x_d, y_d)$. Altfel, va rămâne pe loc.

Cerință

Scrieți un program care, cunoscând $N$ și $M$, respectiv matricea, determină:

Cerința 1. O serie de instrucțiuni pe care, dacă Gimi o urmărește, indiferent de poziția lui inițială, ne va garanta faptul că va trece prin căsuța $(x_t, y_t)$ (marcată cu $1$).

Cerința 2. O serie de instrucțiuni pe care, dacă Gimi o urmărește, indiferent de poziția lui inițială, ne va garanta faptul că va trece prin toate celelalte căsuțe marcate cu $1$.

Cerința 3. Cel mai mic număr $P$ astfel încât, primind o serie de $Q$ instrucțiuni pe care, dacă Gimi o urmărește, indiferent de poziția lui de start, ne va garanta faptul că va trece prin toate celelalte căsuțe marcate cu $1$, fără să fie necesară executarea instrucțiunilor de la $P + 1$ la $Q$.

Date de intrare

Fișierul de intrare blind.in conține pe prima linie cerința $C$ care trebuie rezolvată, iar pe a doua linie două numere $N$ și $M$, separate printr-un spațiu. Fiecare dintre următoarele $N$ linii conțin $M$ numere (care au valori numai de $0$ și $1$), separate prin câte un spațiu.

Dacă $C = 1$, următoarea linie va conține două numere $x_t$ și $y_t$, separate printr-un spațiu, reprezentând coordonatele căsuței prin care Gimi va trebui să treacă.

Dacă $C = 3$, următoarea linie va conține un număr natural $Q$, reprezentând numărul de instrucțiuni. Următoarele $Q$ linii vor conține câte două numere naturale $x$ și $y$, separate printr-un spațiu, reprezentând instrucțiunile.

Date de ieșire

Fișierul de ieșire blind.out va conține pentru $C = 1$ și $C = 2$ seria de instrucțiuni, în ordinea executării lor. Pe fiecare linie se vor afla câte două numere $(x, y)$. Pentru $C = 3$ fișierul va conține numărul minim de instrucțiuni cerut.

Punctarea cerințelor 1 și 2

Punctajul obținut pe fiecare test depinde de numărul de instrucțiuni afișate.

Notăm cu $K$ numărul de căsuțe de $1$ din matrice, iar cu $L_i$ numărul de instrucțiuni afișate. Fie $L_{\max} = 10 \ 000 \ 000$, iar $T = K$ dacă $C = 1$, sau $T = 3K$ dacă $C = 2$. Dacă $L_i > L_{\max}$, atunci punctajul obținut este $0$. Pentru punctaj maxim, $L_i < T$.

Se va acorda punctaj parțial dacă nu se respectă condițiile de mai sus. Se pot obține de la $10\%$ până la $90\%$ din punctaj. Procentajul se calculează după următoarea formulă:

Restricții și precizări

• $C \in \{1, 2, 3\}$
• $1 \leq N, M \leq 500$; Liniile și coloanele sunt numerotate începând cu $1$.
• $1 \leq K \leq 20 \ 000$
• Pentru cerința 3, $1 \leq Q \leq 2 \ 500 \ 000$.
• Se garantează că, printr-un șir de instrucțiuni, se poate ajunge din orice căsuță marcată cu $1$ în oricare alta.
• Dacă Gimi se află inițial în căsuța $(x, y)$, atunci se consideră că Gimi a trecut deja prin acea căsuță.

Exemplul 1

blind.in

1
2 3
1 1 0
0 1 1
2 2

blind.out

1 2
2 2

Explicație

Pentru primul exemplu, analizăm fiecare poziție de start:

• $(1, 1) \to (1, 2) \to (2, 2)$
• $(1, 2) \to (1, 2) \to (2, 2)$
• $(2, 2) \to (1, 2) \to (2, 2)$
• $(2, 3) \to (2, 3) \to (2, 2)$

Toate traseele trec prin căsuța $(2, 2)$ cel puțin odată. De precizat că, dacă Gimi s-ar fi aflat inițial în căsuța $(2, 2)$, atunci se consideră ca el deja a trecut prin acea căsuță. De asemenea, se observă că atunci când Gimi se află în celula $(2, 3)$ și primește instrucțiunea de a se deplasa în celula $(1, 2)$, acesta practic stă pe loc.

Exemplul 2

blind.in

2
2 3
1 1 0
0 1 1

blind.out

1 2
2 2
2 3
2 2
1 2
1 1

Explicație

Pentru al doilea exemplu, analizăm fiecare poziție de start:

• $\underline{(1, 1)} \to \underline{(1, 2)} \to \underline{(2, 2)} \to \underline{(2, 3)} \to (2, 2) \to (1, 2) \to (1, 1)$
• $\underline{(1, 2)} \to (1, 2) \to \underline{(2, 2)} \to \underline{(2, 3)} \to (2, 2) \to (1, 2) \to \underline{(1, 1)}$
• $\underline{(2, 2)} \to \underline{(1, 2)} \to (2, 2) \to \underline{(2, 3)} \to (2, 2) \to (1, 2) \to \underline{(1, 1)}$
• $\underline{(2, 3)} \to (2, 3) \to \underline{(2, 2)} \to (2, 3) \to (2, 2) \to \underline{(1, 2)} \to \underline{(1, 1)}$

Toate traseele trec prin fiecare căsuță marcată cu $1$ cel puțin odată. Pentru fiecare traseu, apar subliniate căsuțele prin care Gimi trece pentru prima oară.

Exemplul 3

blind.in

3
2 3
1 1 0
0 1 1
7
1 2
2 2
2 3
2 2
1 2
1 1
1 2

blind.out

6

Explicație

Pentru al treilea exemplu, primele $6$ instrucțiuni ne garantează faptul că, indiferent de poziția de start a lui Gimi, el va vizita toate celelalte căsuțe. Efectuarea celei de-a $7$ instrucțiuni nu este necesară.