Задача на поиск луж в матрице

@unspoken · Регистрация: 07.08.2013

Студворк — интернет-сервис помощи студентам

Всем доброго дня.
Есть задача, который день бьюсь, не могу придумать алгоритм.

"Consider a matrix of integers MxN, where each value represents a height
of imaginary landscape. Now, the whole figure is put into the water,
deep enough to cover the highest peak, and is brought back to the light.
Write a program to compute puddles remained in the landscape."

Идеи на сегодняшний момент таковы. Нужно отсортировать по убыванию высоты и послойно "вытаскивать" матрицу из воды. Допустим, максимальная высота 500. Создаем пустую матрицу, идентичную по размерам исходной. Проверяем, где в исходной матрице есть "столбы" с высотой 500, в этом месте новой матрицы ставим 1. Если в текущей точке высота не 500, в новой матрице пишем ноль.

Таким образом, для каждой высоты получим матрицу из нулей и единиц.

Теперь задача сводится к нахождению замкнутых контуров с нулями в новой матрице, это и будут искомые лужи.

Проблема состоит в том, что я не могу подобрать нужный алгоритм для поиска этих самых контуров. Потому что лужа может быть и формы кольца, и лужа в луже в луже... Идей возникает куча, но все они нерабочие. =\

@Dimension · 27.10.2015, 17:17

Сообщение от unspoken

где в исходной матрице есть "столбы" с высотой 500, в этом месте новой матрицы ставим 1. Если в текущей точке высота не 500, в новой матрице пишем ноль.

не правда ведь , в матрице может быть несколько высот не равных 500 но их не затопит

@unspoken · 27.10.2015, 17:26 **[ТС]**

не правда ведь , в матрице может быть несколько высот не равных 500 но их не затопит

Не совсем поняла, о чем речь.

@Dimension · 27.10.2015, 17:30

надеюсь я правильно понял задачу . есть матрица

где не должно быть луж по вашему?

@unspoken · 27.10.2015, 17:36 **[ТС]**

Их нигде не будет, они за края выльются.

Лужи будут в случае, например, таком:

C++
1
2
3
4
3 2 3 2 3
3 1 0 1 3    // вот здесь
3 1 0 1 3    // и здесь будет лужа
3 2 3 2 3

@unspoken · 27.10.2015, 17:43 **[ТС]**

Вот картинка, которая может помочь визуализировать задачу.

@Redzep · 28.10.2015, 16:51

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <iostream>
#include <ctime>
#include <windows.h>
#include <vector>
 
//////////////////////////////////
//Функции WinAPI
 
void setColor(int text, int background)
{
    HANDLE hStdOut = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleTextAttribute(hStdOut, (WORD)((background << 4) | text));
}
 
//////////////////////////////////
//////////////////////////////////
 
 
 
struct h
{
    int height;
    bool isChecked;
    bool puddle;
};
 
 
 
//Преобразование координат в номер одномерного массива.
int coordToNum (int i, int j, int width)
{
    return i*width + j;
}
    
 
 
//Проверить выливается ли вода за края матрицы из данной точки.
bool findEdge(std::vector<h>* field, int width, int i, int j, int H)
{
    if (i == 0 || j == 0 || i == field->size()/width - 1 || j == width - 1) return 1;
    (*field)[coordToNum(i, j, width)].isChecked = 1;
 
    if ((H >= (*field)[coordToNum(i + 1, j, width)].height ) && ( (*field)[coordToNum(i + 1, j, width)].isChecked == 0) ) if (findEdge ( field,  width, i + 1, j, H )) {(*field)[coordToNum(i, j, width)].isChecked = 0; return 1;}
    if ((H >= (*field)[coordToNum(i - 1, j, width)].height ) && ( (*field)[coordToNum(i - 1, j, width)].isChecked == 0) ) if (findEdge ( field,  width, i - 1, j, H )) {(*field)[coordToNum(i, j, width)].isChecked = 0; return 1;}
    if ((H >= (*field)[coordToNum(i, j + 1, width)].height ) && ( (*field)[coordToNum(i, j + 1, width)].isChecked == 0) ) if (findEdge ( field,  width, i, j + 1, H )) {(*field)[coordToNum(i, j, width)].isChecked = 0; return 1;} 
    if ((H >= (*field)[coordToNum(i, j - 1, width)].height ) && ( (*field)[coordToNum(i, j - 1, width)].isChecked == 0) ) if (findEdge ( field,  width, i, j - 1, H )) {(*field)[coordToNum(i, j, width)].isChecked = 0; return 1;}
 
    (*field)[coordToNum(i, j, width)].isChecked = 0;
    return 0;
}
 
 
 
//Заполнить лужу из данной точки.
void fill(std::vector<h>* field, int width, int i, int j, int H)
{
    (*field)[coordToNum(i, j, width)].isChecked = 1;
    (*field)[coordToNum(i, j, width)].puddle = 1;
 
    if ((H >= (*field)[coordToNum(i + 1, j, width)].height ) && ( (*field)[coordToNum(i + 1, j, width)].isChecked == 0) ) fill ( field,  width, i + 1, j, H );
    if ((H >= (*field)[coordToNum(i - 1, j, width)].height ) && ( (*field)[coordToNum(i - 1, j, width)].isChecked == 0) ) fill ( field,  width, i - 1, j, H );
    if ((H >= (*field)[coordToNum(i ,j + 1, width)].height ) && ( (*field)[coordToNum(i, j + 1, width)].isChecked == 0) ) fill ( field,  width, i, j + 1, H );
    if ((H >= (*field)[coordToNum(i ,j - 1, width)].height ) && ( (*field)[coordToNum(i, j - 1, width)].isChecked == 0) ) fill ( field,  width, i, j - 1, H );
    (*field)[coordToNum(i, j, width)].isChecked = 0;
}
 
 
 
int main()
{
    int const WIDTH = 20;
    int const LENGTH = 20;
    int const MAX_HEIGTH = 10;
 
    std::vector<h> F;
 
 
    //Заполнить случайными высотами.
    srand(time(0));
    for (int i = 0; i < LENGTH*WIDTH; i++)
    {
        h tmp;
        tmp.height = rand()%MAX_HEIGTH;
        tmp.isChecked = 0;
        tmp.puddle = 0;
 
        F.push_back(tmp);
    }
 
    //Для всех точек матрицы проверить выливается ли вода за края из данной точки, и если не выливается, то заполнить лужу из данной точки.
    for (int i = 0; i < LENGTH; i++)
    {
        for (int j = 0; j < WIDTH; j++)
        {
            if (findEdge ( &F, WIDTH, i, j, F[coordToNum(i, j, WIDTH)].height ) == 0) fill (&F, WIDTH, i, j, F[coordToNum(i, j, WIDTH)].height);
        }
    }
 
 
    //Вывод матрицы.
    for (int i = 0; i < LENGTH; i++)
    {
        for (int j = 0; j < WIDTH; j++)
        {
            if (F[coordToNum(i, j, WIDTH)].puddle == 1) setColor(9, 0);
            else setColor(15, 0);
            std::cout << F[coordToNum(i, j, WIDTH)].height << " ";
        }
        std::cout << std::endl;
    }
 
    std::cout << std::endl;
    system("pause");
}

Задача интересная, поэтому захотел решить ее. Получилось конечно не идеально. Алгоритм проходит каждую точку, нужно как-нибудь оптимизировать цикл и рекурсию (после размера 30 на 30 считает уже довольно долго), но сейчас мне уже лень, главное решил. Для наглядности раскрасил лужи (Используется винапи).

@unspoken · 29.10.2015, 16:21 **[ТС]**

Сообщение от Redzep

Задача интересная, поэтому захотел решить ее.

Как же просто ларчик открывался! Просто и красиво)
А я огород городила с поиском замкнутого контура, поиском точки в полигоне... =)
Гран мерси!

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@unspoken 41 / 0 / 0 Регистрация: 07.08.2013 Сообщений: 41

	Задача на поиск луж в матрице 27.10.2015, 17:11. Показов 2229. Ответов 7 Метки нет (Все метки) Всем доброго дня. Есть задача, который день бьюсь, не могу придумать алгоритм. "Consider a matrix of integers MxN, where each value represents a height of imaginary landscape. Now, the whole figure is put into the water, deep enough to cover the highest peak, and is brought back to the light. Write a program to compute puddles remained in the landscape." Идеи на сегодняшний момент таковы. Нужно отсортировать по убыванию высоты и послойно "вытаскивать" матрицу из воды. Допустим, максимальная высота 500. Создаем пустую матрицу, идентичную по размерам исходной. Проверяем, где в исходной матрице есть "столбы" с высотой 500, в этом месте новой матрицы ставим 1. Если в текущей точке высота не 500, в новой матрице пишем ноль. Таким образом, для каждой высоты получим матрицу из нулей и единиц. Теперь задача сводится к нахождению замкнутых контуров с нулями в новой матрице, это и будут искомые лужи. Проблема состоит в том, что я не могу подобрать нужный алгоритм для поиска этих самых контуров. Потому что лужа может быть и формы кольца, и лужа в луже в луже... Идей возникает куча, но все они нерабочие. =\ 0

@unspoken 41 / 0 / 0 Регистрация: 07.08.2013 Сообщений: 41
	27.10.2015, 17:43 [ТС]
	Вот картинка, которая может помочь визуализировать задачу. Миниатюры 0

Задача на поиск луж в матрице

Решение