Flood protection - FloodFill or is there a better way?

Question

I am doing tasks for practicing and improving skills, but I'm having hard time solving this one:

You have a map with size w * h. On each box of this map is wall(flood protection) or nothing. Water can flow in eight directions and flows on each box at the edges of the map. Of course, water can not flood the box where is built flood protection. You will get size of the map, number of walls and position of each wall.

At the beginning the map is empty. Your task is after placing each piece of the wall tell how big area is protected from water.

So, I have code that works. But too slow. Limits are : size of the map w and h (1≤w,h≤2000)
number of walls : n (1≤n≤w×h)

I tried 8-way FloodFill algorithm and then I improved it to 8-way ScanlineFill. It is just too slow, it runs out of time in half of the test entries. I will post my code if you will want it.
So my question is: How can I improve my algorithm to be even faster? Or am I completely wrong with my choice of algorithms and there is a better way? Thanks for your suggestions.

Test entry:

Input:

4 4  //size w and h
10   // number of walls
1 1  //position of wall - first x, second y  coordinate;
1 2
1 3
2 1
2 3
3 1
3 2
3 3
2 2
3 4

Output:

1  //how big are is covered against flood
2
3
4
5
6
7
9
9
10

Explanation of example input: The first 8 part of the wall of flood protect area size 3 x 3. The ninth part has absolutely no effect, because the box (2,2) has already been protected. The tenth part does not conclude any territory and therefore would contribute only its surface(add only 1).

My code:

#include<iostream>

using namespace std;
int **ostrov;
int area;

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

//The scanline floodfill algorithm using our own stack routines, faster
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++;
            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;
    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;  //actual color
    int prev = 0; //last color
    for (int i = 0; i < n; i++) {
        color++;
        suc = color % 2;
        prev = (color - 1) % 2;
        int x, y;
        cin >> x >> y;
        if (ostrov[y][x] == act) {
            cout << (w * h) - area << endl;
            color--;
            continue; 
        }
        area = 0;
        ostrov[y][x] = 5;
        floodFillScanlineStack(0, 0, act, prev); 
        cout << (w * h) - area << endl;
    }
}

EDIT: Now I realized that this enclosed area doesn't need to be rectangle or square, it could be polygon. Also, there could be more polygons in the map. And after I get a coordinates of part of the wall I must tell:
1.) if it make some polygon(enclosed area) - if yes, how big area which was't enclosed before I must add to are which was enclosed;
2.) if it doesn't make some polygon and it isn't in area which was already enclosed, add to enclosed area number 1(because this box of map water can't flood);
3.) if it is in area which was already enclosed, add nothing, because it doesn't enclose any more area.

Answer 1

Here's a thought that might help. The only way to enclose more space than is occupied by the walls themselves is to create a closed path of some kind. Consider what performing a 4-way flood fill starting at the point a new wall segment is placed would accomplish. It would (with minor modification) allow you to detect a closed path - and alert you to the fact that there are non-wall spaces which are safe from flooding.

Really, this will probably be better to think about as a sort of depth-first search where you're looking for the original point to appear a second time. You'll want to continue the search as one new wall segment may complete a number of closed paths (actually, this is probably not true; to be a barrier against 8-way floodfill, the last required piece of wall would only belong to one new loop formed (unless you were placing it inside some other shape already formed).

Once you have detected a closed loop, you need only fill in the interior squares with some other color (if white is blank and black is walls, maybe red or something); any future walls on red squares don't help. Figuring out how to fill the interior is now the only problem - and it's an easy one at that. Simply check squares all around the new wall. Once you find a square, scan either horizontally or vertically (depending on your direction from point) and see if you cross over the path again. If you cross through an odd number of times, you're inside the shape; if an even number of times, you're outside. There will be some blank space(s) around the new wall piece that completes a closed path, since otherwise, any loop must already have been closed.

Phew. I think that should be significantly faster than flood-filling at each iteration. Still not a walk in the park, but some food for thought.