---
# System prepended metadata

title: Posest

---

# Posest

Tata Tonči, pridelovalec zelja iz Zeljendola, si že dlje časa lasti veliko njivo pravokotne oblike. Njivo lahko predstavimo kot matriko dimenzij $N \times M$, kjer eno polje v matriki predstavlja 1 kvadratni meter njive. 

Vsa polja v matriki so predstavljena kot bodisi posejana ali neposejana. Dve polji sta povezani, če imata skupno stranico. Vsa povezana neposejana polja predstavljajo prazno zaplato njive. 

Tončiju je z zamudo vzklilo še $K$ sadik, zato te prosi, da mu jih pomagaš posaditi tako, da bo na koncu na njivi karseda mnogo praznih zaplat.

## Naloga

Ta naloga je oblike `zgolj-izhod`. Podane so vhodne datoteke (`input_01.txt`, `input_02.txt`, `input_03.txt`, `input_04.txt`, `input_05.txt`), vaša naloga je, da naložite pritične izhodne datoteke (`output_01.txt`, `output_02.txt`, `output_03.txt`, `output_04.txt`, `output_05.txt`).

## Vhod

V prvi vrstici vhodne datoteke sa nahajajo tri naravna števila: $N$ - dolžina njive, $M$ - širina njive in in $K$ - število sadik. 

V vsaki od naslednjih $N$ vrstic se nahaja $M$ znakov. Vsak znak v matriki lahko predstavlja sadiko ali prazno zemljo. Če je znak na presečišču $i$-te vrstice in $j$-tega stolpca `x`, se na tem polju nahaja sadika. Nasprotno, če je znak na presečišču $i$-te vrstice in $j$-tega stolpca `.`, se na tem polju nahaja prazna zemlja.

## Izhod

Vsaka tvoja izhodna datoteka naj vsebuje matriko dimenzij $N \times M$. Vsako polje je lahko `x` (sadika), `.` (zemlja) ali `o` (nova sadika).

## Primer

### Vhod

```
4 8 3
.x...x..
.x.x.x..
.x...xxx
.xxxxx..
```

### Izhod

```
.x...x..
.xoxox..
ox...xxx
.xxxxx..
```

### Komentar primera

Njiva je dimenzij $4 \times 8$. Spremenimo lahko največ $3$ polja. Na začetku so na posesti $4$ prazne zaplate. Ko postavimo sadike na polja s koordinatami $(3,1)$, $(2,3)$ in $(2,5)$, je na posesti $6$ praznih zaplat.

## Komentar k nalogi

- Vse izhodne datoteke morajo biti v opisani obliki. V datoteki ne sme biti znaka, ki ni `x`, `.` ali `o`
- V matriki se znak `o` ne sme pojaviti več kot $K$-krat
- Znak `o` se lahko nahaja le na polju, kjer je bil na vhodu znak `.`
- Če se na nekem polju v izhodni matriki nahaja znak `x` ali`.`, se mora isti znak nahajati v vhodni matriki.

## Točkovanje

Podanih je $5$ vhodnih datotek.

- Prvi primer (`01.in`) je vreden 10 točk
- Drugi primer (`02.in`) je vreden 20 točk
- Tretji primer (`03.in`) je vreden 20 točk
- Četrti primer (`04.in`) je vreden 25 točk
- Peti primer (`05.in`) je vreden 25 točk

Tvoja rešitev se točkuje v primerjavi z rešitvijo komisije. Rešitev komisije je vredna 100 točk. Za vsak odstotek slabšo rešitev izgubite 10 točk (če je vaša rešitev slabša za 10% ali več, rešitev ne prinaša točk). Če je vaša rešitev boljša (ali enako dobra) od rešitve komisije, prejmete 100 točk.

Rezultati komisije po datotekah (torej rešitve, po katerih se računa točkovanje) so:
1. 18 zaplat
2. 1091 zaplat
3. 1009 zaplat
4. 14566 zaplat
5. 46103 zaplat