TAKMIČENJA IZ PROGRAMIRANJA


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.

osmosmerka.cpp    1,106 b      izvorni kod rešenja
osmosmerka.tests.7z    165,691 b      test primeri

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.

Ilustracija za smerove.

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

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.

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;   
}