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; 
    cin >> height >> width;
    vector<vector<char>> obrazok;

    // HORE, DOLE, VPRAVO, VĽAVO
    int limity[4] = {-1, -1, -1, -1};

    for (int i=0; i < height; i++) {
        obrazok.push_back({});
        for (int j=0; j < width; j++) {
            char a;
            cin >> a;
            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;
            }
            obrazok[i].push_back(a);
        }
    }

    limity[0]--;
    limity[1]++;
    limity[2]++;
    limity[3]--;

    if (limity[0] >= 0 && limity[3] >= 0 &&
        limity[1] < height && limity[2] < width) {
        for (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;
                obrazok[i][j] = '#';
            }
        }

        for (auto i : obrazok) {
            for (auto j : i) {
                cout << j;
            }
            cout << endl;
        }
    } else {
        cout << "Neda sa" << endl;
    }
        
    return 0;
}

Riešenie v pythone mohlo vyzerať napríklad takto:

height, width = map(int, input().split())

limity = [-1, -1, -1, -1]
obrazok = []

for i in range(height):
    obrazok.append(list(input()))
    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
            
limity[0]-=1
limity[1]+=1
limity[2]+=1
limity[3]-=1

if (limity[0] >= 0 and limity[3] >= 0 and
        limity[1] < height and limity[2] < width):
    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")

  1. “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ť.