Zadanie
Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Adamovi na [email protected]
V múzeu praskov dostali novú zbierku obrazov. Podľa popisu zásielky majú obsahovať mozaiky rôznych veľkostí a tvarov. Kurátor múzea a jeho tím však potrebujú rýchlo zistiť ktoré časti plátna zapĺňajú takéto mozaiky, aby ich mohli vystaviť. Výstavu potrebujú otvoriť o jeden ďeň a nemajú dostatok času na manuálnu kontrolu, preto o pomoc požiadali vás. Keďže stroj na rezanie plátna potrebuje špeciálne značenie, je nutné každú mozaiku orámovať.
Úloha
Vašou úlohou je napísať program, ktorý na vstupe dostane obraz veľkosti \(r \times s\) znakov. Každý obraz pozostáva zo znakov anglickej abecedy a bodiek (.
). Bodka znamená, že na danom mieste sa nenachádza časť mozaiky. V obraze je potrebné mozaiku nájsť a čo najtesnejšie ju orámovať obdĺžnikom tvoreným zo znakov mriežky (#
). Mozaika nemusí byť súvislá, môže obsahovať “diery”, vždy však stačí použiť iba jeden rám.
Formát vstupu
Na prvom riadku sa nachádzajú dve čísla \(r\) a \(s\) (platí \(1 \leq r, s \leq 800\)), výška a šírka obrazu. Na nasledujúcich \(r\) riadkoch sa nachádza reťazec dĺžky \(s\) pozostávajúci zo znakov anglickej abecedy a bodiek (.
). Môžete počítať s tým, že obraz nie je prázdny, teda obsahuje aspoň jeden znak odlišný od bodky.
Formát výstupu
V prípade, že mozaiku ide zarámovať, vypíšte obraz zo vstupu obsahujúci orámovanie zložené zo znakov #
(\(r\) riadkov po \(s\) znakoch). Ak by rám presahoval rozmery obrazu, vypíšte na jediný riadok výstupu Neda sa
.
Príklad
Input:
4 4
....
.xy.
.zq.
....
Output:
####
#xy#
#zq#
####
Input:
4 4
....
..a.
..a.
.b..
Output:
Neda sa
(Mozaiku nejde orámovať, pretože jeden z jej znakov (b
) sa dotýka steny obrazu. Rám by tak presahoval obraz.)
Input:
7 6
......
......
..aa..
......
..bb..
......
......
Output:
......
.####.
.#aa#.
.#..#.
.#bb#.
.####.
......
Input:
18 30
..............................
..............................
...........qqj................
...........qqq................
........j..kqqk.j--...jpkqp...
........qqkkq-qkqq-p-kkqkp....
..kqkk---qqkk--k-kk-p-kp......
...j-qqkkkk---ppp-p-kkjjjj....
......-qqk------------kqqkp...
....kqqqqq---prask--kk-pj.....
.......pqk----------kp........
......kqkkqqqppkk-pp-k-.......
....jqqqk-jpqpkkp-k-ppkkj.....
...jqk-j...pqkk....pkk--kp....
...........pqkj......j-kkq-...
............pj..........j-k-..
..............................
..............................
Output:
..............................
.############################.
.#.........qqj..............#.
.#.........qqq..............#.
.#......j..kqqk.j--...jpkqp.#.
.#......qqkkq-qkqq-p-kkqkp..#.
.#kqkk---qqkk--k-kk-p-kp....#.
.#.j-qqkkkk---ppp-p-kkjjjj..#.
.#....-qqk------------kqqkp.#.
.#..kqqqqq---prask--kk-pj...#.
.#.....pqk----------kp......#.
.#....kqkkqqqppkk-pp-k-.....#.
.#..jqqqk-jpqpkkp-k-ppkkj...#.
.#.jqk-j...pqkk....pkk--kp..#.
.#.........pqkj......j-kkq-.#.
.#..........pj..........j-k-#.
.############################.
..............................
Táto úloha bola náročná skôr jej implementáciou ako znalosťou algoritmov a potrebných postupov. Bolo počas nej nutné spracovať a upravovať väčšie mnočstvo textových dát.
Teória
Pri riešení je dôležité si uvedomiť aké informácie potrebujeme na zarámovanie jednej mozaiky. Keďže zo zadania vieme, že mozaika bude vždy len jedna stačí nám zistiť jej výšku, šírku a polohu v priestore - potom budeme schopný okolo nej vytvoriť rám. Všetky tieto údaje vieme nahradiť aj štyrmi najvzdialenejšími bodmi (hranicami) od jej stredu, ktoré budú teda reprezentovať miesta, kde vykreslíme 4 steny obdĺžnikového rámu. Nájsť sa dajú rôzne, ale v najhoršom prípade, budú mať riešenia vždy časovú zložitosť \(O(n^2)\). Čo vôbec nieje problém, keďže už len vykresľovanie výstupu z pamäte bude mať rovnakú časovú zložitosť.
Tieto štyri hranice mozaiky vieme nájsť postupne zametaním1 z každej strany, alebo počas jednej
iterácie za stáleho sledovania znakov patriacich mozaike. Čo vlasten
znamená, že pri každom znaku sa pozriem, či náhodou nieje zatiaľ
najvzdialenejší od stredu, resp. najbližší k jednej zo stien plátna. Ak
to je takýto bod, tak si ho zapmätám a ďalej hľadám body, ktoré sú
lepšie ako tento. Následne pri vykresľovaní výsledného obrázku, budeme
dbať na medze vyhradené hranicami a namiesto bodiek dosadíme na správne
miesta znaky #
.
Riešenie
Riešenie v c++ mohlo vyzerať napríklad takto:
#include <bits/stdc++.h>
using namespace std;
int main() {
int width, height;
>> height >> width;
cin <vector<char>> obrazok;
vector
// HORE, DOLE, VPRAVO, VĽAVO
int limity[4] = {-1, -1, -1, -1};
for (int i=0; i < height; i++) {
.push_back({});
obrazokfor (int j=0; j < width; j++) {
char a;
>> a;
cin if (a != '.') {
if (limity[0] > i || limity[0] == -1) limity[0] = i;
if (limity[1] < i || limity[1] == -1) limity[1] = i;
if (limity[2] < j || limity[2] == -1) limity[2] = j;
if (limity[3] > j || limity[3] == -1) limity[3] = j;
}
[i].push_back(a);
obrazok}
}
[0]--;
limity[1]++;
limity[2]++;
limity[3]--;
limity
if (limity[0] >= 0 && limity[3] >= 0 &&
[1] < height && limity[2] < width) {
limityfor (int i=limity[0]; i <= limity[1]; i++) {
for (int j=limity[3]; j <= limity[2]; j++) {
if (limity[1] > i && i > limity[0] && limity[2] > j && j > limity[3]) continue;
[i][j] = '#';
obrazok}
}
for (auto i : obrazok) {
for (auto j : i) {
<< j;
cout }
<< endl;
cout }
} else {
<< "Neda sa" << endl;
cout }
return 0;
}
Riešenie v pythone mohlo vyzerať napríklad takto:
= map(int, input().split())
height, width
= [-1, -1, -1, -1]
limity = []
obrazok
for i in range(height):
list(input()))
obrazok.append(for j in range(width):
if (obrazok[i][j] != '.'):
if (limity[0] > i or limity[0] == -1): limity[0] = i
if (limity[1] < i or limity[1] == -1): limity[1] = i
if (limity[2] < j or limity[2] == -1): limity[2] = j
if (limity[3] > j or limity[3] == -1): limity[3] = j
0]-=1
limity[1]+=1
limity[2]+=1
limity[3]-=1
limity[
if (limity[0] >= 0 and limity[3] >= 0 and
1] < height and limity[2] < width):
limity[for i in range(limity[0], limity[1]+1, 1):
for j in range(limity[3], limity[2]+1, 1):
if (limity[1] > i and i > limity[0] and limity[2] > j and j > limity[3]): continue
= '#'
obrazok[i][j] for i in obrazok:
for j in i:
print(j, end="")
print()
else:
print("Neda sa")
“Zametanie” sa nazýva technika počas ktorej postupne prechádzam z jednej strany na druhú a zaznamenámvam si počet výskytov hľadaných znakov, alebo čísel.↩︎
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.