防洪 - 此时，floodFill或是否有更好的办法？ [英] Flood protection - FloodFill or is there a better way?
问题描述
我在做任务的实践和提高技能，但我有很难解决这一个：
您有尺寸宽*高的地图。在这张地图上的每一个盒壁（洪水 保护），还是一无所获。水可以在八个方向和流量流向 在每个框中的地图的边缘。当然，水不能淹没 其中，建防洪盒子。你会得到的地图大小， 墙数量和每面墙的位置。
在开始的映射为空。你的任务是把每一个后 一块墙告诉有多大的区域，距离水保护。
所以，我有code，它的工作原理。但太慢。限制是：在地图W和H（1≤w，h≤2000）
的大小
墙壁编号：n（1≤n≤w×高）
我试过8路此时，floodFill算法，然后我提高到8路ScanlineFill。这实在是太慢了，它运行的时间缩短了一半的测试项。我会后我的code，如果你想要它。
所以我的问题是：我怎样才能提高我的算法，以更快的速度？还是我完全错了我的选择算法，有一个更好的办法？感谢您的建议。
测试条目：
输入：
4 4 //大小w和h
10 //一些墙壁
1 1 //位置墙体的 - 第一个x，第二个y坐标;
1 2
1 3
2 1
2 3
3 1
3 2
3 3
2 2
3 4
输出：
1 //多大覆盖抗洪
2
3
4
五
6
7
9
9
10
例如输入说明：第8部分洪水的墙 保护区大小3×3第九部分完全没有影响， 因为该框（2,2）已经被保护。第十部分做 没有达成任何领土，因此只能将有助于其 表面（只添加1）。
我的code：
＃包括＆LT;的iostream＆GT;
使用名字空间std;
INT **奥斯特罗夫;
INT区;
＃定义的stackSize 16777216
INT堆栈[的stackSize]
INT stackPointer;
INT H; W;
布尔流行（INT
＆功放; X，INT和放大器; Y）
{
如果（stackPointer大于0）
{
INT P =堆叠[stackPointer]
X为对/小时;
Y = P％H;
stackPointer--;
返回1;
}
其他
{
返回0;
}
}
布尔推（INT X，int y）对
{
如果（stackPointer＆LT;的stackSize - 1）
{
stackPointer ++;
堆叠[stackPointer] = H * X + Y;
返回1;
}
其他
{
返回0;
}
}
无效emptyStack（）
{
INT X，Y;
而（POP（X，Y））;
}
//用我们自己的堆栈程序的扫描线此时，floodFill算法，速度更快
无效floodFillScanlineStack（INT X，INT Y，INT newColor，INT oldColor）
{
如果（oldColor == newColor）回报;
emptyStack（）;
INT Y1;
布尔spanLeft，spanRight，spanDDLeft，spanDDRight，spanDULeft，spanDURight;
如果收益率（按（X，Y）！）;
而（POP（X，Y））
{
Y1 = Y;
而（Y1＆GT; = 0＆功放;＆放大器;奥斯特罗夫[X] [Y1] == oldColor）y1--;
Y1 ++;
spanLeft = spanRight = spanDDLeft = spanDDRight = spanDULeft = spanDURight = 0;
而（Y1＆LT;的H＆amp;＆放大器;奥斯特罗夫[X] [Y1] == oldColor）
{
如果（奥斯特罗夫[X] [Y1] == oldColor）
pocet ++;
奥斯特罗夫[X] [Y1 = newColor;
如果（spanLeft＆安培;＆放大器，X＆GT; 0安培;＆安培;！奥斯特罗夫[X - 1] [Y1] == oldColor）
{
（！推（X - 1，Y1）），如果回报;
spanLeft = 1;
}
否则，如果（spanLeft＆安培;＆放大器，X＆GT; 0安培;＆安培;！奥斯特罗夫[X - 1] [Y1 = oldColor）
{
spanLeft = 0;
}
如果（spanRight＆安培;＆放大器，X＆LT;W¯¯ - 1安培;！＆放大器;奥斯特罗夫[X + 1] [Y1] == oldColor）
{
（！推（X + 1，Y1）），如果回报;
spanRight = 1;
}
否则，如果（spanRight＆安培;＆放大器，X＆LT;W¯¯ - 1安培;＆放大器;奥斯特罗夫[X + 1] [Y1 = oldColor！）
{
spanRight = 0;
}
如果（！spanDDLeft＆安培;＆安培，X大于0和安培;＆安培; Y1 + 1＆其中;的H＆amp;＆安培;奥斯特罗夫[X - 1] [Y1 + 1] == oldColor）
{
（！推（X - 1，Y1 + 1）），如果回报;
spanDDLeft = 1;
}
否则如果（spanDDLeft＆安培;＆安培，X大于0和安培;＆安培; Y1 + 1＆其中;的H＆amp;＆安培;！奥斯特罗夫[X - 1] [Y1 + 1] = oldColor）
{
spanDDLeft = 0;
}
如果（spanDDRight＆安培;！＆安培; X + 1＆其中w为安培;＆安培; Y1 + 1＆其中;的H＆amp;＆安培;奥斯特罗夫〔X + 1] [Y1 + 1] == oldColor）
{
（！推（X + 1，Y1 + 1））如果返回;
spanDDRight = 1;
}
否则如果（spanDDRight＆安培;＆安培; X + 1＆其中w为安培;＆安培; Y1 + 1＆其中;的H＆amp;＆安培;！奥斯特罗夫〔X + 1] [Y1 + 1] = oldColor）
{
spanDDRight = 0;
}
如果（spanDULeft＆安培;＆安培，X大于0和安培;＆安培; Y1大于0＆安培;＆安培;！奥斯特罗夫[X - 1] [Y1 - 1] == oldColor）
{
（！推（X - 1，Y1 - 1）），如果回报;
spanDULeft = 1;
}
否则如果（spanDULeft＆安培;＆安培，X大于0和安培;＆安培; Y1大于0＆安培;＆安培;！奥斯特罗夫[X - 1] [Y1 - 1] = oldColor）
{
spanDULeft = 0;
}
如果（spanDURight＆安培;＆安培; X + 1＆其中w为安培;＆安培; Y1大于0＆安培;＆安培;！奥斯特罗夫〔X + 1] [Y1 - 1] == oldColor）
{
（！推（X + 1，Y1 - 1）），如果回报;
spanDURight = 1;
}
否则如果（spanDURight＆安培;＆安培; X + 1＆其中w为安培;＆安培; Y1大于0＆安培;＆安培;！奥斯特罗夫〔X + 1] [Y1 - 1] = oldColor）
{
spanDURight = 0;
}
Y1 ++;
}
}
}
诠释的main（）
{
CIN＆GT;＆GT; h取代;＆GT;瓦;
H + = 2;
W + = 2;
奥斯特罗夫=新INT * [W]
的for（int i = 0; I＆LT;瓦;我++）{
奥斯特罗夫[I] =新INT并[h];
对于（INT J = 0; J＆LT; H，J ++）
奥斯特罗夫[I] [J] = 1;
}
INT N;
CIN＆GT;＆GT; N;
INT颜色= 1;
INT行动= 0; //实际的颜色
INT preV = 0; //最后的颜色
的for（int i = 0;我n种;我++）{
颜色++;
SUC =颜色％2;
preV =（颜色 - 1）％2;
INT X，Y;
CIN＆GT;＆GT; X - GT;＆GT; ÿ;
如果（奥斯特罗夫[Y] [X] ==行为）{
COUT＆LT;＆LT; （W * H） - 区 - LT;＆LT; ENDL;
颜色 - ;
继续;
}
面积= 0;
奥斯特罗夫[Y] [X] = 5;
floodFillScanlineStack（0，0，行为，preV）;
COUT＆LT;＆LT; （W * H） - 区 - LT;＆LT; ENDL;
}
}
编辑：
现在我才知道这封闭区域并不需要是长方形或正方形，也可以是多边形。此外，有可能在地图更多边形。及后，我收到了坐标的墙上，我必须告诉的一部分：
1），如果它做出一些多边形（封闭区域） - 如果是的话，有多大面积这was't封闭之前，我必须补充到是这是封闭的;
2。）如果不进行一些多边形，它不是在其中已经封闭区域，添加封闭的区域号码1（因为此框地图水不能淹没）;
3.）如果是在区域这是已经封闭，添加什么，因为它不围绕任何更大的面积。
下面有一个想法，这可能有助于。括更多的空间的唯一方式是比由壁占用本身是创建某种封闭路径。考虑一下进行4路洪水填充的开始在点新墙段放在的将完成。这将（带小的修改）允许您检测封闭路径 - 并提醒您的是，也有非壁舱，则洪水安全
说真的，这将可能是更好的去思考作为一种深度优先搜索，在那里你正在寻找原点出现第二次。你要继续寻找为一体的新型墙体段可以完成多项封闭路径（实际上，这可能是不正确的，是对此时，floodFill 8路的障碍，最后需要的一块墙只会属于一个新的循环形成了（除非你在里面已经形成了一些其他形状放置）。
一旦检测到闭环，你只需要填写一些其他颜色的内饰广场（如果白是空白的，黑色的墙壁，说不定红色或东西）;在红色方块任何未来的墙壁没有帮助。搞清楚如何填补内部是现在唯一的问题 - 这是一个很容易的一个。只需点击方块周围所有的新墙。一旦你找到一个正方形，扫描水平或垂直（取决于从点的方向），看看你是否越过了路了。如果您通过的次数为奇数跨，你是里面的造型;如果偶数次，则在外面。会有一些空白空间（S）围绕完成闭合路径的新型墙体片，否则，任何环路必须已经被关闭。
唷。我觉得应该比洪水灌在每次迭代显著更快。不过不是在公园里散步，但有些耐人寻味。
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.
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.
这篇关于防洪 - 此时，floodFill或是否有更好的办法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
