3

问题定义如下：给你一个正方形。广场内衬有大小为 1m x 1m 的扁平石板。草地环绕着广场。石板可能处于不同的高度。开始下雨了。确定将在哪里创建水坑并计算将包含多少水。水不会流过角落。在任何面积的草地上都可以随时浸泡任何体积的水。

输入：

宽高

width*height 非负数，描述每块石板在草地上的高度。

输出：

水坑中的水量。

width*height 标志描述了将创建水坑和不会创建水坑的地方。

. - 没有水坑

# - 水坑

例子

输入：

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) 的有趣算法。

4

2 回答 2

2

概括

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

该算法将遍历地图中的所有高度，在每个高度执行洪水填充操作。

细节

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

  1. 如果邻居高度 <= x，则将所有高度为 x 的石板连接到它们的邻居（在不相交集数据结构中存储连接的石板集）

  2. 删除任何连接到草地的集合

  3. 将剩余集合中所有高度为 x 的石板标记为水坑

  4. 将剩余集合中的石板总数加到总 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)。

于 2013-05-31T20:28:01.717 回答
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;
}

16 x 16 文件：

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

8 x 8 文件

11111111
11111111
11011111
11110111
11111111
11000011
11111111
11111111

你可以通过做几件事来轻松地优化这个算法。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

这些是结果：

11111111
10000001
10111101
10100101
10110101
10110101
10000101
11111111

现在，当我们删除底部的 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
于 2013-05-31T20:53:14.093 回答