Matrice Palindrom

Time limit: 1s Memory limit: 256MB Input: Output:

Se dă o matrice binară pătratică AA de dimensiuni N×NN \times N cu elemente din mulțimea {0,1}\{0, 1\}. Începi din celula (0,0)(0, 0) — colțul stânga-sus — cu un șir SS, inițial gol, și vrei să ajungi în celula (N1,N1)(N − 1, N − 1) — colțul dreapta-jos. La fiecare mutare te poți deplasa în jos sau la dreapta cu o celulă. Pentru fiecare celulă prin care treci (inclusiv prima și ultima) adaugi valoarea din celula respectivă la capătul din dreapta al șirului SS.

Cerință

Determinați dacă este posibil ca șirul SS astfel obținut să fie palindrom. Dacă da, determinați o succesiune de mutări în jos și/sau la dreapta care duce din celula (0,0)(0, 0) în celula (N1,N1)(N − 1, N − 1) pentru care șirul obținut este palindrom. Pentru această succesiune, determinați în ordine celulele parcurse.

Pentru că ne place de voi, am decis să vă anunțăm că matricea a fost generată aleator.

Date de intrare

Pe prima linie se află un singur număr întreg NN, reprezentând latura matricii.

Următoarele NN linii conțin câte NN caractere din mulțimea {0,1}\{0, 1\}, neseparate prin spații, reprezentând descrierea matricii.

Se garantează că matricea este aleasă uniform aleator dintre toate matricile binare de dimensiuni N×NN \times N.

Date de ieșire

Afișați NO dacă nu se poate ca SS să fie palindrom. Altfel, afișați YES pe prima linie, apoi, pe fiecare dintre următoarele 2N12N − 1 linii, afișați două valori, iki_k și jk (0ik,jk<N)j_k \ (0 ≤ i_k, j_k < N ) — coordonatele celei de-a kk-a celule parcurse.

Restricții și precizări

  • 1N5 0001 \leq N \leq 5 \ 000
  • Ai,j{0,1}A_{i, j} \in \{0, 1\} pentru 0i,j<N0 \leq i, j < N
# Punctaj Restricții
1 5 1N101 \leq N \leq 10
2 9 1N1001 \leq N \leq 100
3 19 1N5001 \leq N \leq 500
4 27 1N1 5001 \leq N \leq 1 \ 500
5 40 Fără restricții suplimentare.

Exemplul 1

stdin

2
01
00

stdout

YES
0 0
0 1
1 1

Explicație

Obținem șirul 010, care este palindrom.

Exemplul 2

stdin

4
0100
1010
0100
0001

stdout

NO

Explicație

Nu se poate obține un șir palindrom.

Exemplul 3

stdin

4
0010
1001
1010
0010

stdout

YES
0 0
0 1
0 2
0 3
1 3
2 3
3 3

Explicație

Obținem șirul 0010100, care este palindrom.

Log in or sign up to be able to send submissions!