Защита от наводнений — FloodFill или есть лучший способ?

Я делаю задания для отработки и улучшения навыков, но мне трудно решить эту проблему:

У вас есть карта размером w * h. На каждой коробке этой карты есть стена (наводнение
защита) или ничего. Вода может течь в восьми направлениях и течет
на каждом поле по краям карты. Конечно, вода не может затопить
Коробка, где построена защита от наводнений. Вы получите размер карты,
количество стен и положение каждой стены.

В начале карта пуста. Ваша задача после размещения каждого
Кусочек стены расскажет, насколько большая площадь защищена от воды.

Итак, у меня есть код, который работает. Но слишком медленно. Ограничения: размер карты w и h (1≤w, h≤2000)
количество стен: n (1≤n≤w × h)

Я попробовал 8-способный алгоритм FloodFill, а затем улучшил его до 8-способного ScanlineFill. Это слишком медленно, у него заканчивается время в половине тестовых записей. Я опубликую свой код, если вы захотите.
Итак, мой вопрос: как я могу улучшить свой алгоритм, чтобы быть еще быстрее? Или я совершенно не прав с моим выбором алгоритмов и есть лучший способ? Спасибо за ваши предложения.

Тестовая запись:

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

Объяснение примера ввода: первые 8 частей стены наводнения
защитная зона размером 3 х 3. Девятая часть не имеет абсолютно никакого эффекта,
потому что коробка (2,2) уже была защищена. Десятая часть делает
не заключать какую-либо территорию и, следовательно, будет способствовать только его
поверхность (добавить только 1).

Мой код:

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

РЕДАКТИРОВАТЬ:
Теперь я понял, что эта закрытая область не обязательно должна быть прямоугольной или квадратной, это может быть многоугольник. Кроме того, на карте может быть больше многоугольников. И после того, как я получу координаты части стены, я должен сказать:
1.) если он образует какой-то многоугольник (закрытая область) — если да, то какая большая область, которая не была заключена до того, как я должен добавить, является вложенной;
2.) если он не образует какой-либо многоугольник и не находится в области, которая уже была закрыта, добавьте в закрытую область номер 1 (потому что этот ящик с водой карты не может затопить);
3.) если он находится в области, которая уже была заключена, ничего не добавляйте, поскольку она больше не ограничивает область.