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

1

これはうまく機能しているようです。アイデアは、エッジにエスケープできる「外向きの流れ」があるかどうかを確認する再帰関数であるということです。そのようなエスケープがない値がパドルする場合。2 つの入力ファイルでテストしたところ、非常にうまく機能しました。これら 2 つのファイルの出力をコピーしました。グローバル変数の私の厄介な使用を許してください。

    #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 に答える