поиск "островов" на графе

[Euler7]

Доброго времени суток. Помогите пожалуйста составить алгоритм. Не могу нормально сформулировать задачу, поэтому покажу частный случай, т.к. сдаётся мне алгоритм у них один.
Есть тайловая карта:

нужно выделить "острова", т.е. получить такую карту:

Карта может быть большой, так что сложность алгоритма критична...
Это явно делается в 2 прохода по карте, на первом нужно разметить карту и составить список зон на объединение, а на втором объединить нужные зоны, но вот конкретный алгоритм не получается составить(точнее получается, но там уж очень много вложенных циклов выходит).

[Mysterious Light]

Мб, просто обходом в ширину по графу, в котором вершины — ячейки, а ребра соединяют смежные ячейки одного не белого цвета.
Берём первую «не классифицированную» цветную ячейку, делаем обход в ширину, попутно помечая все пройденные вершины как первый остров, берём следующую непройденную цветную ячейку, делаем от неё обход в ширину и т.д.
Получится два вложенных цикла (внешний — по номеру острова, внутренний — по ячейкам каждого отдельного острова)

[Null]

Посмотрите на эту статью. Там есть раздел про поиск компонент связности на изображении.

[Euler7]

Спасибо, пока остановился на обходе в ширину, вариант оказался достаточно производительным, а вот мой вменяемой скорости так и не показал.

[Alexu007]

Euler7 в сообщении #961044 писал(а):

Доброго времени суток. Помогите пожалуйста составить алгоритм. Не могу нормально сформулировать задачу, поэтому покажу частный случай, т.к. сдаётся мне алгоритм у них один.
т.е. получить такую карту:
Карта может быть большой, так что сложность алгоритма критична...

Делается это рекурсией. Допустим 0 - белый квадрат, 1 - синий, 2 - красный.

1. перебираете свою карту до нахождения первого цветного квадрата (в моём примере > 0) - карту по-любому придётся перебрать всю от начала до конца - это к вопросу сложности алгоритма.

2. Начало функции: запоминаете, какой цвет вы нашли, прибавляете что-нить к найденному квадрату, например +10, теперь там 11 (или 12 если первый был найден красный)

3. Ищите в диапазоне +- 1 от найденного квадрата, тут нужно отслеживать выход за пределы поля (меньше нуля, больше макс.), можно не проверять диагонали - если обе переменные не равны 0, и центр - если обе равны 0. Если находите ещё квадрат нужного цвета (цвет вы запомнили в начале) - вызываете снова функцию пункт 2.

И так далее до конца поля. Чтобы ваши найденные поля отличались, прибавлять можно разные цифры: +10, +20, +30 и так далее.

Надеюсь что понятно.

[arseniiv]

Чудесная спецификация поиска в глубину, да ещё и с рекурсией! Мне бы так советы научиться раздавать…

[Alexu007]

Рекурсией ищутся соприкасающиеся торцами квадратики одного цвета. А что не так то? По моему так самое обычное применение рекурсии.

[arseniiv]

Бессмысленное. Поиск в глубину — цикл и стек. Поиск в ширину (упомянутый выше Mysterious Light) — цикл и очередь. От цикла вместо рекурсии в данном случае одни плюсы. Ну и, плюс, в глубину вместо ширины тут, вроде как, похуже.

Как вас тянет советы давать…

[Alexu007]

arseniiv в сообщении #961674 писал(а):

Бессмысленное. Поиск в глубину — цикл и стек. Поиск в ширину (упомянутый выше Mysterious Light) — цикл и очередь. От цикла вместо рекурсии в данном случае одни плюсы. Ну и, плюс, в глубину вместо ширины тут, вроде как, похуже.

Как вас тянет советы давать…

У нас прямоугольная (квадратная) карта, на которой нужно перебрать все ячейки - потому что комп не может посмотреть на неё издалека и увидеть, что в "левом нижнем углу ничего нет, и искать там не нада". В условиях задачи ничего не сказано о местоположении и количестве цветных ячеек, может быть всего одна в нижнем правом углу карты, и её нужно найти. Поэтому вложенный цикл и перебираем последовательно всю карту в поиске интересующих нас цветных ячеек.

Объясните пжалста, что означает поиск в ширину, или (тем более) в глубину?

Далее, при нахождении цветной ячейки - получили её адрес на карте, две переменные. Ваши действия?

[Skeptic]

Euler7 в сообщении #961044 писал(а):

Это явно делается в 2 прохода по карте, на первом нужно разметить карту и составить список зон на объединение, а на втором объединить нужные зоны, но вот конкретный алгоритм не получается составить(точнее получается, но там уж очень много вложенных циклов выходит).

Размечать карту не нужно, она и так уже размечена.
Нужно выделить зоны, и записать отдельно. Форма записи зоны должна упрощать последующую обработку.
Сложности программы бояться не следует - она зависит от алгоритма. А вот алгоритм должен быть прозрачным.

Основная процедура - просмотр окружения ячейки. Это простая программа, просматривающая примыкающие горизонтальные и вертикальные ячейки, и выдающая адреса ячеек того же цвета. Адреса найденных ячеек запоминаются в области, отведённой для зоны.
Перебор ячеек карты производится последовательно.

Отлаживать программу удобно на образе буквы Ш, поворачивая её $90^\circ$.

В данном алгоритме заведомо много дублированных действий, но они устранятся на стадии оптимизации.

P.S. Привлечение понятий теории графов излишне, они не облегчают программирование, без них даже проще.

[arseniiv]

Skeptic в сообщении #962046 писал(а):

Привлечение понятий теории графов излишне, они не облегчают программирование, без них даже проще.

Вилами по воде, если язык не допотопный. А оптимизацию потом сделать успеем.

Alexu007 в сообщении #961843 писал(а):

Объясните пжалста, что означает поиск в ширину, или (тем более) в глубину?

Погуглите depth-first search (DFS) и breadth-first search (BFS).

Alexu007 в сообщении #961843 писал(а):

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

Это к чему? Да, просмотра каждой клетки хотя бы раз не избежать, и чего?

Вложенный (если имелся в виду кратный) цикл — это тоже вилами. Цикл по перебору всех клеток может быть и одинарным, это совершенно бессмысленное уточнение.

[Alexu007]

Да можно и без цикла, для каждой ячейки свой код писать и последовательно выполнять - и тоже работать будет. Всё-таки программы пишут как проще и понятнее. Вот код на Си, который делает примерно то же: ищет и помечает слипшиеся боками квадраты (взято из морского боя, функция считает количество палуб в корабле):

Используется синтаксис C++

//функция определяет число палуб у корабля без учета угловых клеток
//получает координаты первой найденой палубы x, y
//возвращает в Cx_Palube число палуб у корабля
//---------------------------------------------------------------------------
void Detect_One_Ship_01(int x, int y)
  {
  int x1, y1;

  //прибавляем 1 к счетчику палуб корабля
  Cx_Palube++;

  //устанавливаем в найденную палубу 2 вместо 1, чтобы не считать еще раз
  pole_Homo[X][Y] = 2;

  for (int i = -1; i < 2; i++)
    {
    x1 = x + i;
    if ((x1 < 0) || (x1 == Rz)) continue;

    for (int j = -1; j < 2; j++)
      {
      y1 = y + j;
      if ((y1 < 0) || (y1 == Rz)) continue;

      // не проверяем углы
      if ((i != 0) && (j != 0)) continue;

      //рекурсивно вызываем функцию Detect_OneShip
      if (pole_Homo[x1][y1] == 1) Detect_One_Ship_01(x1, y1);
      }
    }

  }



  for (int i = 0; i < Rz; i++)
    for (int j = 0; j < Rz; j++)
      if (pole_Homo[i][j] == 1)
        {
        Cx_Palube = 0;

        // вызов функции
        Detect_One_Ship_01(i, j);
        }

[venco]

Alexu007, вы ознакомились с особенностями поиска в глубину и в ширину? Поняли недостатки поиска в глубину? Мне кажется, что нет. Иначе не приводили бы в качестве примера морской бой, где размер острова сильно ограничен.

[Skeptic]

venco в сообщении #962838 писал(а):

Alexu007, вы ознакомились с особенностями поиска в глубину и в ширину? Поняли недостатки поиска в глубину? Мне кажется, что нет. Иначе не приводили бы в качестве примера морской бой, где размер острова сильно ограничен.

venco, как может Alexu007 понять недостатки поиска в глубину, если на его просьбу объяснить это никто не откликнулся? Может быть вы поясните что такое поиск в глубину, а заодно, и в ширину?


Alexu007
Программы после написания обычно выполняют, чтобы убедиться в их правильности. Где в вашей программе указаны координаты первой палубы?
Зачем без нужды применять рекурсию? Для усложнения программы или наукообразия? Пишите проще.

[Alexu007]

Программа "Морской Бой" прекрасно работает, я просто вытащил функцию из неё. Координаты первой палубы передаются в функцию как параметры - там внизу есть пример вызова функции из программы. Затем эта функция ищет "вокруг себя" и если находит - вызывает сама себя уже с новыми координатами. И так далее, пока есть что находить. Найденые палубы помечает другой цифрой. Уж куда проще - не надо ничего запоминать, никаких координат, к которым нужно будет вернуться, никаких дополнительных буферов памяти для их хранения. Никакой путаницы. Нашёл любую первую попавшуюся палубу, "натравил" на неё функцию - и она не успокоится, пока не "перекусает" весь корабль.