Submit solution

Points: 1
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Nabavili smo jednu od super-upijajućih krpi sa jednog od tv shop-ova i želimo da je testiramo. Krpa je pravougaonog oblika i ima šare u obliku vertikalnih i horizontalnih linija koje je dele na n×m podudarnih kvadratića. Test se sastoji od prolivanja mastila na neke od n×m kvadratića krpe (svaki kvadratić je ili uprljan mastilom ili potpuno čist na početku) i merenja vremena za koje će krpa upiti svo mastilo.

Naravno, ispostavlja se da je krpa skupa i beskorisna. Osim xto ne upija leto kako treba, ona doprinosi njegovom razlivanju. Preciznije, svake sekunde leto se razliva na susedne, čiste kvadratiće (tj. svaki čist kvadratić koji u toj sekundi ima bar jednog uprljanog suseda postaje uprljan mastilom) a u isto vreme krpa upija ono što je do tada bilo uprljano mastilom (tj. svaki uprljani kvadratić postaje čist). Dva kvadratića su susedna ako dele zajedničku stranicu.

Pošto smo razočarani krpom, a ne želimo da nam eksperiment propadne, odlučili smo da predvidimo kako će krpa izgledati posle t sekundi.

Ulaz:

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu ulazne datoteke nalaze se 3 prirodna broja n, m i t koji predstavljaju, redom, dimenzije krpe i vreme (u sekundama) posle kog nas interesuje izgled krpe (1 ≤ n, m ≤ 103, 1 ≤ t ≤ 106). Sledećih n redova sadrže niz od m cifara iz skupa {0, 1} bez razmaka - izgled krpe nakon početnog prolivanja mastila. 1 označava da se na odgovarajućem mestu nalazi uprljan kvadratić, a 0 čist kvadratić.

Izlaz:

(Izlazni podaci se ispisuju na standardni izlaz) U prvih n redova izlazne datoteke ispisati po m cifara iz skupa {0, 1} bez razmaka - izgled krpe nakon t sekundi. 1 i 0 imaju isto značenje kao na ulazu.

Primer:

standardni ulaz      standardni izlaz
4 5 2
01001
00000
10000
00000
        
01001
00110
10101
01000

Objašnjenje.

Za dati test primer, promena krpe je prikazana na slikama:

Ilustracija za rešenje. Ilustracija za rešenje. Ilustracija za rešenje.
Početak Posle 1 sekunde Posle 2 sekunde

Napomena.

U 25% test primera biće 1 ≤ n, m, t ≤ 200. Zbog veličine ulaza, C/C++ kodovi bi trebalo da učitavaju cele redove.


Comments

There are no comments at the moment.