Code Submission Evaluation System Login

Algoritmit ongelmanratkaisussa 2019

Ruudukko


Task | Statistics


CSES - RuudukkoCSES - Ruudukko

Time limit:1.00 s Memory limit:512 MB

Annettuna on $n \times n$ -ruudukko, jonka joissakin ruuduissa on kolikko. Voit joka siirrolla poistaa kaikki kolikot tietyltä riviltä tai sarakkeelta.

Mikä on pienin määrä siirtoja, joiden jälkeen ruudukko on tyhjä?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $n$: ruudukon koko. Ruudukon rivit ja sarakkeet on numeroitu kokonaisluvuin $1,2,\dots,n$.

Tämän jälkeen syötteessä on $n$ riviä, jotka kuvaavat ruudukon. Jokaisella rivillä on $n$ merkkiä: . (tyhjä) tai o (kolikko).

Tuloste

Tulosta ensin kokonaisluku $k$: pienin siirtojen määrä. Tulosta tämän jälkeen $k$ riviä, jotka kuvaavat siirrot.

Tulosta jokaisella rivillä ensin $1$ (rivi) tai $2$ (sarake) ja sitten rivin tai sarakkeen numero. Voit tulostaa minkä tahansa kelvollisen ratkaisun.

Rajat
Esimerkki

Syöte:
3
..o
o.o
...


Tuloste:
2
1 2
2 3