Osmosmerka

View as PDF

Submit solution

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

Author:
Problem type

Data je osmosmerka koja umesto slova ima brojeve (od 0 do 104). Nisu poznate reči koje treba da se nađu u osmosmerci, ali zato znamo za svaku reč gde počinje, koliko je dugačka i u kom smeru se prostire. Vaš zadatak je da pomoću tih podataka rešite osmosmerku, odnosno da pronađete polja koja ne pripadaju nijednoj od tih reči (polja koja bi ostala neprecrtana).

Ulaz:

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu ulazne datoteke se nalaze dimenzije osmosmerke n i m (n, m ≤ 100). Zatim se u svakom od narednih n redova nalazi po m brojeva - oni predstavljaju sadržaj osmosmerke. Sledi red u kome se nalazi broj k (k ≤ 10.000), broj reči koje se nalaze u osmosmerci. U svakom od narednih k redova se nalaze po četiri broja i, j, s i l, što znači da odgovarajuća reč počinje sa polja (i, j), ide u smeru s i dužine je l. Prvo polje u osmosmerci je polje (1, 1). Smer je broj od 1 do 8 i svaki od njih odgovara smerovima kao na slici.

Ilustracija za smerove.

Izlaz:

(Izlazni podaci se ispisuju na standardni izlaz) U prvom redu izlazne datoteke treba da se nalazi broj t, ukupan broj neprecrtanih polja osmosmerke. Zatim u narednih t redova treba ispisati vrednosti u tim poljima, onim redosledom kojim se javljaju ako se posmatra red po red osmosmerke, svaki od njih sleva na desno.

Primer:

standardni ulaz      standardni izlaz
3 4
2 5 1 4
3 0 1 5
4 9 2 4
5
3 3 8 3
3 2 2 3
2 3 7 2
3 1 1 1
2 1 3 2
        
4
5
1
5
4

Ilustracija za rešenje.

Objašnjenje.

Na slici je prikazano kako izgleda rešena osmosmerka. Može se videti da su neprecrtani brojevi redom 5, 1, 5, 4.

Napomena.

U 40% test primera postojaće samo smerovi 1, 3, 5, 7.


Comments

There are no comments at the moment.