Обход матрицы

@systemcorp · Регистрация: 20.05.2013

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

Здравствуйте, пишу примитивную 2D игру и столкнулся со следующей проблемой: после генерации ландшафта у меня создается матрица из 1 и 2(1-вода, 2-земля). Необходимо что бы программа могла находить отдельные острова их границы и присваивать им номера.К примеру дана следующая матрица:
1 2 2 2 2 2 1 1 1 1
1 1 2 2 2 2 2 1 1 1
1 2 2 2 1 2 1 1 1 2
1 1 2 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 2 2 2 1 1
1 1 1 1 2 2 2 2 1 1
1 2 1 1 1 1 2 2 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 2
Как сделать, что бы программа по отдельности нашла все острова:
1 2 2 2 2 2 1 1 1 1
1 1 2 2 2 2 2 1 1 1
1 2 2 2 1 2 1 1 1 2
1 1 2 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 2 2 2 1 1
1 1 1 1 2 2 2 2 1 1
1 2 1 1 1 1 2 2 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 2
Для себя, как вариант я нашел след.алгоритм: создаю такую же матрицу и заполняю ее нулями. Прохожу по исходному массиву начиная с 0 ячейки, если на исходной матрице встречаю "2", а на второй "0", то запоминаю эту координату (означает, что найдена земля, но до этого мы ее не находили). Затем смотрю правый, нижний и левый блок, от того что мы нашли и так прохожу по матрицам до того, пока координаты текущего блока не совпадут с первоначально найденым.
И этот алгоритм работает до тех пор, пока мы не попадаем в так называемый тупик, этот тупик можно увидеть в красном острове(вторая строка, крайняя красная цифра "2") попадая на эту клетку справа от нее нет земли, снизу тоже, а слева мы уже были. Как можно избежать такие тупики?

@Toros1992 · 15.10.2017, 11:49

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private void CheckLand(LandScape[,] Map, LandScape currentLand, List<LandScape> Island)
{
    Island.Add(currentLand);
    List<LandScape> LandsToCheck = new List<LandScape>();
    for(int i = -1; i <= 1; i++)
    {
        for(int j = -1; i <= 1; i++)
        {
        try{
             LandScape Land = Map[currentLand.X + i, currentLand.Y + j];
             if(!Island.Contains(Land) && Land.IsLand())
                 ChekLand(Map, Land, Island);
             }
        catch{} //для пропуска пограничных случаев с выходом за пределы карты
        }
    {
}

Можно сделать подобный метод. Он рекурсивно проходит по клеткам одного острова.
Соответственно подразумевается наличие класса LandScape с реализацией интерфейса IEquatable<LandScape>, полями X и Y, индексатором и методом IsLand(). А также при вызове описанного метода нужно проверять, является ли данная клетка землёй и не принадлежит ли она уже какому то острову.

Новые блоги и статьи Все статьи Все блоги /
Загрузка PNG-файла с альфа-каналом с помощью библиотеки SDL3_image на Android 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом

@systemcorp 2 / 2 / 2 Регистрация: 20.05.2013 Сообщений: 27

	Обход матрицы 15.10.2017, 10:22. Показов 1057. Ответов 1 Метки нет (Все метки) Здравствуйте, пишу примитивную 2D игру и столкнулся со следующей проблемой: после генерации ландшафта у меня создается матрица из 1 и 2(1-вода, 2-земля). Необходимо что бы программа могла находить отдельные острова их границы и присваивать им номера.К примеру дана следующая матрица: 1 2 2 2 2 2 1 1 1 1 1 1 2 2 2 2 2 1 1 1 1 2 2 2 1 2 1 1 1 2 1 1 2 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 1 1 1 1 1 1 2 2 2 2 1 1 1 2 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 Как сделать, что бы программа по отдельности нашла все острова: 1 2 2 2 2 2 1 1 1 1 1 1 2 2 2 2 2 1 1 1 1 2 2 2 1 2 1 1 1 2 1 1 2 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 1 1 1 1 1 1 2 2 2 2 1 1 1 2 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 Для себя, как вариант я нашел след.алгоритм: создаю такую же матрицу и заполняю ее нулями. Прохожу по исходному массиву начиная с 0 ячейки, если на исходной матрице встречаю "2", а на второй "0", то запоминаю эту координату (означает, что найдена земля, но до этого мы ее не находили). Затем смотрю правый, нижний и левый блок, от того что мы нашли и так прохожу по матрицам до того, пока координаты текущего блока не совпадут с первоначально найденым. И этот алгоритм работает до тех пор, пока мы не попадаем в так называемый тупик, этот тупик можно увидеть в красном острове(вторая строка, крайняя красная цифра "2") попадая на эту клетку справа от нее нет земли, снизу тоже, а слева мы уже были. Как можно избежать такие тупики? 0

Обход матрицы

Решение