- 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
- 1 \le n \le 100
Esimerkki
Syöte:
3 ..o o.o ...
Tuloste:
2 1 2 2 3