在正方形上找到所有的水坑（算法）

Question

在正方形上找到所有的水坑（算法）

c++calgorithmcomplexity-theory

3

问题定义如下：给定一个正方形，正方形被1m x 1m的平坦石板所覆盖。石板可能高度不同。周围是草地。开始下雨了。确定哪里会形成水坑并计算其中包含多少水。水不会通过角落流走。在任何草地区域都可以随时吸收任何数量的水。

输入：宽度高度宽度*高度的非负数描述每个石板相对于草地高度的高度。

输出：水坑中的水量。宽度*高度个符号，描述哪些位置会产生水坑，哪些位置不会。 . - 没有水坑 # - 水坑

示例：输入：

8 8
0 0 0 0 0 1 0 0 
0 1 1 1 0 1 0 0
0 1 0 2 1 2 4 5 
0 1 1 2 0 2 4 5 
0 3 3 3 3 3 3 4 
0 3 0 1 2 0 3 4 
0 3 3 3 3 3 3 0 
0 0 0 0 0 0 0 0

输出：

11
........
........
..#.....
....#...
........
..####..
........
........

输入：

16 16
8 0 1 0 0 0 0 2 2 4 3 4 5 0 0 2
6 2 0 5 2 0 0 2 0 1 0 3 1 2 1 2
7 2 5 4 5 2 2 1 3 6 2 0 8 0 3 2
2 5 3 3 0 1 0 3 3 0 2 0 3 0 1 1
1 0 1 4 1 1 2 0 3 1 1 0 1 1 2 0
2 6 2 0 0 3 5 5 4 3 0 4 2 2 2 1
4 2 0 0 0 1 1 2 1 2 1 0 4 0 5 1
2 0 2 0 5 0 1 1 2 0 7 5 1 0 4 3
13 6 6 0 10 8 10 5 17 6 4 0 12 5 7 6
7 3 0 2 5 3 8 0 3 6 1 4 2 3 0 3
8 0 6 1 2 2 6 3 7 6 4 0 1 4 2 1
3 5 3 0 0 4 4 1 4 0 3 2 0 0 1 0
13 3 6 0 7 5 3 2 21 8 13 3 5 0 13 7
3 5 6 2 2 2 0 2 5 0 7 0 1 3 7 5
7 4 5 3 4 5 2 0 23 9 10 5 9 7 9 8
11 5 7 7 9 7 1 0 17 13 7 10 6 5 8 10

输出：

103
................
..#.....###.#...
.......#...#.#..
....###..#.#.#..
.#..##.#...#....
...##.....#.....
..#####.#..#.#..
.#.#.###.#..##..
...#.......#....
..#....#..#...#.
.#.#.......#....
...##..#.#..##..
.#.#.........#..
......#..#.##...
.#..............
................

我尝试了不同的方法。从最大值开始泛洪填充，然后从最小值开始，但这对于每个输入都不起作用或需要代码的复杂化。有什么想法吗？

我对复杂度为O（n ^ 2）或o（n ^ 3）的算法很感兴趣。

- dragon7

提示：计算最小生成树。 - David Eisenstat

但是，如何将一个正方形转换成图形呢？ - dragon7

每块石板都有一个顶点吗？ - Joe Runde

我猜每个边的权重是石板高度之间的差异。但我仍然不理解MST如何找到所有的水坑并计算水的体积。 - dragon7

@BartlomiejLewandowski 他们是那些没有更高路径到边界的人。 MST的相关属性是，对于每对节点s和t，在MST中s-t路径上的最大边权是每个s-t路径的最大边权的下界。 - David Eisenstat

显示剩余2条评论

2个回答

1

这看起来运行得很好。它是一个递归函数，检查是否有“外部流出”可以使其逃到边缘。如果没有这样的逃生通道，值将会聚集。我在您提供的两个输入文件上进行了测试，效果非常好。我为您复制了这两个文件的输出结果。请原谅我的不良全局变量使用等，我认为算法背后的概念才是重要的，而不是良好的代码风格 :)

    #include <fstream>
#include <iostream>
#include <vector>
using namespace std;

int SIZE_X;
int SIZE_Y;


bool **result;
int **INPUT;


bool flowToEdge(int x, int y, int value, bool* visited) {
    if(x < 0 || x == SIZE_X || y < 0 || y == SIZE_Y) return true;
    if(visited[(x * SIZE_X) + y]) return false;
    if(value < INPUT[x][y]) return false;

    visited[(x * SIZE_X) + y] = true;

    bool left = false;
    bool right = false;
    bool up = false;
    bool down = false;


    left = flowToEdge(x-1, y, value, visited);
    right = flowToEdge(x+1, y, value, visited);
    up = flowToEdge(x, y+1, value, visited);
    down = flowToEdge(x, y-1, value, visited);


    return (left || up || down || right);
}

int main() {

    ifstream myReadFile;
    myReadFile.open("test.txt");

    myReadFile >> SIZE_X;
    myReadFile >> SIZE_Y;

    INPUT = new int*[SIZE_X];
    result = new bool*[SIZE_X];
    for(int i = 0; i < SIZE_X; i++) {
        INPUT[i] = new int[SIZE_Y];
        result[i] = new bool[SIZE_Y];
        for(int j = 0; j < SIZE_Y; j++) {
            int someInt;
            myReadFile >> someInt;
            INPUT[i][j] = someInt;
            result[i][j] = false;
        }
    }


    for(int i = 0; i < SIZE_X; i++) {
        for(int j = 0; j < SIZE_Y; j++) {
            bool visited[SIZE_X][SIZE_Y];
            for(int k = 0; k < SIZE_X; k++)//You can avoid this looping by using maps with pairs of coordinates instead
                for(int l = 0; l < SIZE_Y; l++)
                    visited[k][l] = 0;

            result[i][j] = flowToEdge(i,j, INPUT[i][j], &visited[0][0]);
        }
    }

    for(int i = 0; i < SIZE_X; i++) {
        cout << endl;
        for(int j = 0; j < SIZE_Y; j++)
            cout << result[i][j];
    }
    cout << endl;
}

16x16文件：

1111111111111111
1101111100010111
1111111011101011
1111000110101011
1011001011101111
1110011111011111
1100000101101011
1010100010110011
1110111111101111
1101101011011101
1010111111101111
1110011010110011
1010111111111011
1111110110100111
1011111111111111
1111111111111111

8乘8文件

你可以通过几种方式来轻松且大幅度地优化这个算法。A: 找到路径后立即返回true将大大加快速度。您还可以将其全局连接到当前结果集，以便任何给定点只需找到一个已知的流点而不是一直到边缘。

每个n都需要检查每个节点。但是，通过优化，我们应该能够使大多数情况下这个数量远低于n^2，但在最坏的情况下仍然是n^3算法...但是创建它会非常困难（有适当的优化逻辑...动态规划胜利！）

编辑：

修改后的代码适用于以下情况：

8 8
1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 1
1 0 1 1 1 1 0 1
1 0 1 0 0 1 0 1
1 0 1 1 0 1 0 1
1 0 1 1 0 1 0 1
1 0 0 0 0 1 0 1
1 1 1 1 1 1 1 1

这些是结果：

现在，当我们删除底部的1时，希望看不到任何积水。

8 8
1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 1
1 0 1 1 1 1 0 1
1 0 1 0 0 1 0 1
1 0 1 1 0 1 0 1
1 0 1 1 0 1 0 1
1 0 0 0 0 1 0 1
1 1 1 1 1 1 0 1

这些是结果。

1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1

- MobA11y

我认为这不起作用，因为在某些情况下，流向边缘可能需要折返（考虑由1组成的螺旋形）。 - Peter de Rivaz

你可能是对的，但是“重复检查”问题只需要不同的修复方法。不要“接近”初始值，而是不要检查已经检查过的值。这会名义上增加内存需求，但计算复杂度不会更高。 - MobA11y

谢谢 :) 它看起来很不错，但是没有计算水的容量。这是必需的。 - dragon7

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter de Rivaz · Accepted Answer

概述

我会尝试使用不相交集合数据结构来解决这个问题。

算法是在地图上迭代每个高度，对每个高度执行一个泛洪操作。

细节

对于每个高度x（从0开始）

如果相邻标石的高度小于等于x，则将所有高度为x的标石与其相邻标石连接起来（将相连的标石集存储在不相交集合数据结构中）
删除连接到草坪的所有集合
标记仍然存在的集合中高度为x的所有标石为水坑
将剩余集合中的标石总数添加到总数t中

最终t代表水的总体积。

示例

0 0 0 0 0 1 0 0 
0 1 1 1 0 1 0 0
0 1 0 2 1 2 4 5 
0 1 1 2 0 2 4 5 
0 3 3 3 3 3 3 4 
0 3 0 1 2 0 3 4 
0 3 3 3 3 3 3 0 
0 0 0 0 0 0 0 0

将所有高度为0的石板连接成集合A、B、C、D、E、F。

A A A A A 1 B B 
A 1 1 1 A 1 B B
A 1 C 2 1 2 4 5 
A 1 1 2 D 2 4 5 
A 3 3 3 3 3 3 4 
A 3 E 1 2 F 3 4 
A 3 3 3 3 3 3 A 
A A A A A A A A

移除与草连接的石板，并将剩余的标记为水坑。

          1      
  1 1 1   1
  1 C 2 1 2 4 5     #
  1 1 2 D 2 4 5       #
  3 3 3 3 3 3 4 
  3 E 1 2 F 3 4     #     #
  3 3 3 3 3 3

计算剩余集合大小t=4

连接所有高度为1的元素

          G      
  C C C   G
  C C 2 D 2 4 5     #
  C C 2 D 2 4 5       #
  3 3 3 3 3 3 4 
  3 E E 2 F 3 4     #     #
  3 3 3 3 3 3

移除连接到草地的石板，并将剩余的标记为水坑。

      2   2 4 5     #
      2   2 4 5       #
  3 3 3 3 3 3 4 
  3 E E 2 F 3 4     # #   #
  3 3 3 3 3 3

t=4+3=7

连接所有高度为2的元素

      A   B 4 5     #
      A   B 4 5       #
  3 3 3 3 3 3 4 
  3 E E E E 3 4     # #   #
  3 3 3 3 3 3

移除连接到草地的石板，并标记剩余的为水坑。

            4 5     #
            4 5       #
  3 3 3 3 3 3 4 
  3 E E E E 3 4     # # # #
  3 3 3 3 3 3

t=7+4=11

连接所有高度为3的元素

            4 5     #
            4 5       #
  E E E E E E 4 
  E E E E E E 4     # # # #
  E E E E E E

移除连接到草地的石板，并标记其余部分为水坑。

            4 5     #
            4 5       #
              4 
              4     # # # #

完成高度为4和5的操作后，将不会剩下任何内容。

预处理步骤是创建每个高度的所有位置列表，这意味着该算法接近于O(n^2)。