Fie o matrice de dimensiuni 𝑁 × 𝑀 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 (𝑥𝑑 , 𝑦𝑑). 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 (𝑥, 𝑦) sunt (cât timp sunt în matrice): (𝑥 − 1, 𝑦), (𝑥, 𝑦 + 1), (𝑥 + 1, 𝑦) și (𝑥, 𝑦 − 1).

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

Cerința

Scrieți un program care, cunoscând 𝑁 și 𝑀, 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 (𝑥𝑡 , 𝑦𝑡) (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 𝑃 astfel încât, primind o serie de 𝑄 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 𝑃 + 1 la 𝑄.

Date de intrare

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

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

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

Date de ieșire

Fișierul de ieșire blind.out va conține pentru 𝐶 = 1 şi 𝐶 = 2 seria de instrucțiuni, în ordinea executării lor. Pe fiecare linie se vor afla câte două numere (𝑥, 𝑦). Pentru 𝐶 = 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 𝐾 numărul de căsuțe de 1 din matrice, iar cu 𝐿𝑖 numărul de instrucțiuni afișate. Fie 𝐿max = 10 000 000, iar 𝑇 = 𝐾 dacă 𝐶 = 1, sau 𝑇 = 3𝐾 dacă 𝐶 = 2. Dacă 𝐿𝑖 > 𝐿max, atunci punctajul obținut este 0. Pentru punctaj maxim, 𝐿𝑖 < 𝑇.

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ă:

$$ 90 – 80 \times {\left( \frac{\log_{10}{L_i} – \log_{10}{T}}{\log_{10}{L_{max}} – \log_{10}{T}} \right)}^{0.75} $$

Restricții și precizări

• 𝐶 ∈ {1, 2, 3}
• 1 ≤ 𝑁, 𝑀 ≤ 500; Liniile și coloanele sunt numerotate începând cu 1.
• 1 ≤ 𝐾 ≤ 20 000
• Pentru cerința 3, 1 ≤ 𝑄 ≤ 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 (𝑥, 𝑦), atunci se consideră că Gimi a trecut deja prin acea căsuță.

Subtaskuri

• 𝐶 = 1, 𝑁 = 1 și 𝐾 ≠ 𝑁 · 𝑀
• 𝐶 = 1, 𝐾 = 𝑁 · 𝑀
• 𝐶 = 1, 2 ≤ 𝑁 , 𝑀 ≤ 60, 1 ≤ 𝐾 ≤ 100 și 𝐾 ≠ 𝑁 · 𝑀
• 𝐶 = 1, 60 < 𝑁 , 𝑀 ≤ 500, 1 ≤ 𝐾 ≤ 20 000 și 𝐾 ≠ 𝑁 · 𝑀
• 𝐶 = 2, 𝑁 = 1 și 𝐾 ≠ 𝑁 · 𝑀
• 𝐶 = 2, 𝐾 = 𝑁 · 𝑀
• 𝐶 = 2, 2 ≤ 𝑁 , 𝑀 ≤ 60, 1 ≤ 𝐾 ≤ 100 și 𝐾 ≠ 𝑁 · 𝑀
• 𝐶 = 2, 60 < 𝑁 , 𝑀 ≤ 500, 1 ≤ 𝐾 ≤ 20 000 și 𝐾 ≠ 𝑁 · 𝑀
• 𝐶 = 3, 1 ≤ 𝐾 ≤ 100, 1 ≤ 𝑄 ≤ 10 000
• 𝐶 = 3, 100 < 𝐾 ≤ 1 000, 1 ≤ 𝑄 ≤ 100 000
• 𝐶 = 3, 1 000 < 𝐾 ≤ 5 000, 1 ≤ 𝑄 ≤ 500 000
• 𝐶 = 3, 1 000 < 𝐾 ≤ 5 000, 500 000 ≤ 𝑄 ≤ 2 500 000
• 𝐶 = 3, 5 000 < 𝐾 ≤ 8 000
• 𝐶 = 3, 8 000 < 𝐾 ≤ 20 000

Exemplul 1

blind.in

1
2 3
1 1 0
0 1 1
2 2

blind.out

1 2
2 2

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

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 primul exemplu, analizăm fiecare poziție de start:

• (1, 1) → (1, 2) → (2, 2)
• (1, 2) → (1, 2) → (2, 2)
• (2, 2) → (1, 2) → (2, 2)
• (2, 3) → (2, 3) → (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.

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

• (1, 1) → (1, 2) → (2, 2) → (2, 3) → (2, 2) → (1, 2) → (1, 1)
• (1, 2) → (1, 2) → (2, 2) → (2, 3) → (2, 2) → (1, 2) → (1, 1)
• (2, 2) → (1, 2) → (2, 2) → (2, 3) → (2, 2) → (1, 2) → (1, 1)
• (2, 3) → (2, 3) → (2, 2) → (2, 3) → (2, 2) → (1, 2) → (1, 1)

Toate traseele trec prin fiecare căsuță marcată cu 1 cel puțin odată.

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ă.