DRŽAVNO NATJECANJE 2015. – Drugi dan natjecanja / Srednja škola, II. podskupina (3. i 4. razred) - 1. zadatak

Krkod je mlađi gluplji brat popularnog QR koda - dvodimenzionalnog barkoda kojim se informacija zapisuje u vizualnom obliku pogodnom za strojno čitanje.

Za razliku od QR koda, Krkod ne koristi sofisticirane algoritme za enkodiranje podataka i detekciju pogrešaka.

Podaci koje zapisujemo u kod su niz nula i jedinica dok je krkod x matrica koja se sastoji od crnih i bijelih piksela gdje je prirodni broj veći ili jednak od 17.

Matrica se od podataka radi tako da se najprije postave posebne funkcionalne strukture koje ne sadrže informacije nego služe kako bi se odredila lokacija i orijentacija krkoda unutar veće matrice te se nakon toga dodaju same informacije u ostale piksele.

Kutnik je matrica od 7x7 piksela koja se sastoji od 3x3 crne matrice okružene najprije sa kvadratnim rubom bijelih piksela pa zatim još jednim kvadratnim rubom od crnih piksela.

Poravnik je matrica od 5x5 piksela koja se sastoji od jednog crnog piksela okruženog rubom od bijelih te rubom od crnih piksela.

Ove strukture se smještaju u NxN matricu na sljedeći način:

1. U gornji lijevi, gornji desni i donji lijevi kut se postavi po jedan kutnik.
2. U matricu se postavi jedan poravnik tako da mu je sredina u istom stupcu kao lijevi rub desnog kutnika te u istom retku kao gornji rub donjeg kutnika.
3. Svakom kutniku se doda rub od bijelih piksela, osim tamo gdje bi pikseli izašli izvan NxN matrice

Zadani niz nula i jedinica se sada pohranjuje direktno u preostale piksele NxN matrice, i to tako da nula odgovara bijelom pikselu, a jedinica crnom.

Podaci se zapisuju stupac po stupac od zadnjeg (najdesnijeg) prema prvom, a u svakom stupcu odozdo prema gore.

Pikseli koje zauzimaju funkcionalne strukture te im je boja već određena se jednostavno preskaču.

Kada digitalnom kamerom pokušamo očitati kod, najprije slikamo veće područje te zatim pokušavamo pronaći i dekodirati krkod.

U ovom zadatku, slikano područje je također matrica crnih i bijelih piksela te se sastoji od M redaka i M stupaca.

Napišite program koji će u slikanoj matrici piksela pronaći krkod te odrediti informaciju pohranjenu u njemu.

Možete pretpostaviti da je zadana slikana matrica piksela dobivena tako da je najprije konstruiran neki NxN krkod prema pravilima gore, zatim je možda rotiran za neki višekratnik od 90 stupnjeva te smješten u MxM krkod prema pravilima gore, zatim je možda rotiran za neki višekratnik od 90 stupnjeva te smješten u x matricu.

Napomena: Dozvoljeno je da se kutnici i poravnici pojavljuju proizvoljno u matrici ali će vrijediti da unutar matrice postoji točno jedan ispravan krkod.

Ulazni​ podaci

U prvom redu nalazi se prirodni broj, M (17 ≤ M ≤ 100) - broj dijeljenja. - dimenzije matrice. U svakom od sljedećih M redova nalazi se niz od točno M znakova ‘.’ ili ‘#’ - jedan redak matrice.

Znak ‘.’ (točka) predstavlja bijeli piksel dok znak ‘#’ (ljestve) predstavlja crni piksel.

Izlazni podaci

U prvi red ispišite niz znakova ‘0’ ili ‘1’ bez razmaka - informaciju pohranjenu u pronađenom krkodu.

Primjeri test​ podataka

Ulaz

17
#######...#######
#.....#...#.....#
#.###.#...#.###.#
#.###.#.#.#.###.#
#.###.#...#.###.#
#.....#.#.#.....#
#######.#.#######
........#........
..###########.#..
........#...#.##.
#######.#.#.####.
#.....#.#...#.#.#
#.###.#.#####.##.
#.###.#.#..######
#.###.#.###..#.#.
#.....#...#.##.#.
#######....#...##

Izlaz

1001010001111101100001111110111001
0001011001011000100011111010001111
1100

Objašnjenje

Ulaz

20
#######..#.#.##..##.
#.....#.....#..#####
#.###.#...#.###.###.
#.###.#.###...##.#..
#.###.#..######.####
#.....#..##...######
#######..##.#.##....
........###...##..##
......##..######...#
####.#..##.#..#.####
##.##..##.###.###...
..........#.........
#######.#...#######.
#.....#..##.#.....#.
#.###.#.#.#.#.###.##
#.###.#...#.#.###.#.
#.###.#.....#.###.#.
#.....#...#.#.....##
#######.....#######.
.###.#...#.....####.

Izlaz

1100110101011110010000111011101000
1011000111111010111110000110100111
0001001100000011101001011001011110
0111011101100110111000011101011000
00100000

Objašnjenje