Найти все лужи на квадрате (алгоритм)

Кажется, это работает хорошо. Идея состоит в том, что это рекурсивная функция, которая проверяет, существует ли «внешний поток», который позволит ему уйти на край. Если значения, которые не имеют такого выхода, будут лужами. Я проверил его на ваших двух входных файлах, и он работает довольно хорошо. Я скопировал вывод для этих двух файлов для вас. Прошу прощения за мое грязное использование глобальных переменных, а что нет, я решил, что именно концепция, стоящая за алгоритмом, имеет значение, а не хороший стиль 🙂

    #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 на 16:

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

Файл 8 на 8

11111111
11111111
11011111
11110111
11111111
11000011
11111111
11111111

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

Работа включает в себя, каждый 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