Diskuze: Protipovodňová ochrana

V předchozím kvízu, Online test znalostí C++, jsme si ověřili nabyté zkušenosti z kurzu.

Aktivity

Jozef

Člen

Jozef:15.9.2015 19:18

Zdravím, mám problém s nasledujúcou úlohou:

Ostrov si môžeme predstaviť ako obdĺžnik rozdelený na w×h štvorčekov.
Každý štvorček môže byť buď prázdny, alebo na ňom môže byť postavená časť protipovodňovej ochrany.

Voda dokáže tiecť ôsmimi smermi a priteká na každé políčko na okrajoch ostrova.
 Samozrejme, voda nevie zaplaviť políčko, na ktorom je postavená protipovodňová ochrana.

Dostanete rozmery ostrova a pozície, kde sa postupne stavajú múry. Na začiatku je ostrov prázdny. Vašou úlohou je po postavení každého kúsku múra povedať, aká plocha je chránená pred vodou.

Formát vstupu

Na prvom riadku vstupu dostanete dve celé čísla w a h (1≤w,h≤2000), pričom w je šírka a h výška obdĺžnikového ostrova.

Na druhom riadku je číslo n (1≤n≤w×h) – počet štvorcových kúskov protipovodňového múru, ktoré budú postavené.

Každý z nasledujúcich n riadkov obsahuje dve čísla xi a yi (1≤xi≤w, 1≤yi≤h), ktoré označujú pozíciu, na ktorú bude postavený i-ty kúsok múra.

Napadlo ma použiť FloodFill s 8-mi smermi, resp. jeho lepšiu verziu Scanline Flood Fill. Lenže je to príliš pomalé. Ako by sa to dalo riešiť inak?
Vďaka za každý návrh.

Môj kód:

#include<iostream>

using namespace std;
int **ostrov;
int pocet;

#define stackSize 16777216
int stack[stackSize];
int stackPointer;
int h, w;


bool pop(int
    &x, int &y)
{
    if (stackPointer > 0)
    {
        int p = stack[stackPointer];
        x = p / h;
        y = p % h;
        stackPointer--;
        return 1;
    }
    else
    {
        return 0;
    }
}

bool push(int x, int y)
{
    if (stackPointer < stackSize - 1)
    {
        stackPointer++;
        stack[stackPointer] = h * x + y;
        return 1;
    }
    else
    {
        return 0;
    }
}

void emptyStack()
{
    int x, y;
    while (pop(x, y));
}

void floodFillScanlineStack(int x, int y, int newColor, int oldColor)
{
    if (oldColor == newColor) return;
    emptyStack();

    int y1;
    bool spanLeft, spanRight, spanDDLeft, spanDDRight, spanDULeft, spanDURight;

    if (!push(x, y)) return;

    while (pop(x, y))
    {
        y1 = y;
        while (y1 >= 0 &&ostrov[x][y1] == oldColor) y1--;
        y1++;
        spanLeft = spanRight = spanDDLeft = spanDDRight = spanDULeft = spanDURight = 0;
        while (y1 < h && ostrov[x][y1] == oldColor)
        {
            if (ostrov[x][y1] == oldColor)
                pocet++;  //kolko policok vyfarbim
            ostrov[x][y1] = newColor;
            if (!spanLeft && x > 0 && ostrov[x - 1][y1] == oldColor)
            {
                if (!push(x - 1, y1)) return;
                spanLeft = 1;
            }
            else if (spanLeft && x > 0 && ostrov[x - 1][y1] != oldColor)
            {
                spanLeft = 0;
            }
            if (!spanRight && x < w - 1 && ostrov[x + 1][y1] == oldColor)
            {
                if (!push(x + 1, y1)) return;
                spanRight = 1;
            }
            else if (spanRight && x < w - 1 && ostrov[x + 1][y1] != oldColor)
            {
                spanRight = 0;
            }
            if (!spanDDLeft && x > 0 && y1 + 1 < h && ostrov[x - 1][y1 + 1] == oldColor)
            {
                if (!push(x - 1, y1 + 1)) return;
                spanDDLeft = 1;
            }
            else if (spanDDLeft && x > 0 && y1 + 1 < h && ostrov[x - 1][y1 + 1] != oldColor)
            {
                spanDDLeft = 0;
            }
            if (!spanDDRight && x + 1 < w && y1 + 1 < h && ostrov[x + 1][y1 + 1] == oldColor)
            {
                if (!push(x + 1, y1 + 1)) return;
                spanDDRight = 1;
            }
            else if (spanDDRight && x + 1 < w && y1 + 1 < h && ostrov[x + 1][y1 + 1] != oldColor)
            {
                spanDDRight = 0;
            }
            if (!spanDULeft && x > 0 && y1 > 0 && ostrov[x - 1][y1 - 1] == oldColor)
            {
                if (!push(x - 1, y1 - 1)) return;
                spanDULeft = 1;
            }
            else if (spanDULeft && x > 0 && y1 > 0 && ostrov[x - 1][y1 - 1] != oldColor)
            {
                spanDULeft = 0;
            }
            if (!spanDURight && x + 1 < w && y1 > 0 && ostrov[x + 1][y1 - 1] == oldColor)
            {
                if (!push(x + 1, y1 - 1)) return;
                spanDURight = 1;
            }
            else if (spanDURight && x + 1 < w && y1 > 0 && ostrov[x + 1][y1 - 1] != oldColor)
            {
                spanDURight = 0;
            }
            y1++;
        }
    }
}


int main()
{

    cin >> h >> w;
    h += 2;   //pridám z každej strany jednu vrstvu, ktorá slúži ako počiatok toku vody
    w += 2;
    ostrov = new int*[w];
    for (int i = 0; i < w; i++) {
        ostrov[i] = new int[h];
        for (int j = 0; j < h; j++)
            ostrov[i][j] = 1;
    }
    int n;
    cin >> n;
    int color = 1;
    int act = 0;  //súčasná farba
    int prev = 0; //predchádzajúca farba
    for (int i = 0; i < n; i++) {
        color++;
        suc = color % 2;  // striedam farby, ktoré sa budú floodfillom premaľovávať
        prev = (color - 1) % 2;
        int x, y;
        cin >> x >> y;
        if (ostrov[y][x] == act) {   //ak sa nachádza v už chránenej oblasti, môžem zbytok preskočiť
            cout << (w * h) - pocet << endl;
            color--;
            continue;
        }
        pocet = 0;
        ostrov[y][x] = 5;
        floodFillScanlineStack(0, 0, act, prev);
        cout << (w * h) - pocet << endl;  //pocet vsetkych policok - pocet vyfarbenych
    }
}

Odpovědět

15.9.2015 19:18

I'm not afraid to die on a treadmill

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 1 zpráv z 1.

Nejčastěji vyhledáváné

Diskuze: Protipovodňová ochrana