|
Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja
možete slati na e-mail:
tak.prog@gmail.com
U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.
|
logo by Igor Antolović
|
|
|
zadatak: Osmosmerka
|
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 nalaze u datoteci osmosmerka.in.)
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.
Izlaz:
(Izlazne podatke upisati u datoteku osmosmerka.out) 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:
osmosmerka.in
|
|
osmosmerka.out
|
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
|
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.
|
|
fajl: osmosmerka.cpp
|
#include <stdio.h>
#include <stdlib.h>
using namespace std;
const int maxN = 100;
int n, m, k, res;
int tabla[maxN][maxN];
int ti, tj, s, l;
int di[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dj[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int main() {
freopen("osm.in", "r", stdin);
freopen("osm.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%d", &(tabla[i][j]));
res = n * m;
scanf("%d", &k);
for (int t = 0; t < k; t++) {
scanf("%d%d%d%d", &ti, &tj, &s, &l);
s--; ti--; tj--;
for (int tl = 0; tl < l; tl++) {
if (tabla[ti][tj] >= 0) {
tabla[ti][tj] = -1;
res--;
}
ti += di[s];
tj += dj[s];
}
}
printf("%d\n", res);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (tabla[i][j] >= 0)
printf("%d\n", tabla[i][j]);
return 0;
}
|
|
|