Алгоритм нахождения "островов"

Знаю, что решение должно лежать на поверхности, но пока никаких "легких" вариантов в голову не приходит. Собственно, дан двумерный булевый массив со случайным распределением значений. Нужно найти количество "островов", образованных всеми true-значениями, "островом" считается набор true-ячеек, которые соседствуют друг с другом по-вертикали или по-горизонтали (или одна отдельная ячейка). Надеюсь, понятно объяснил Крайне желательно при поиске островов использовать pThreads. Пока приходит в голову только итерация по массиву с запуском потока поиска в случае нахождения true, но тогда количество потоков будет заранее не определено, что нехорошо. Подскажите, пожалуйста, как грамотнее всего решить эту задачу? Язык - C++, система - Linux.

 

Я си плохо знаю поэтому примерно только. Мб так:

Код (Text):

1. int get_num_of_isles(bool* array, int x_max, int y_max)
2. {
3.    int num_of_isles;
4.    for(y=0; y<=y_max; y++)
5.    {
6.       for(x=0; x<=x_max; x++)
7.       {
8.           if(array[x][y])
9.           {
10.              num_of_isles++;
11.              array[x][y]=false; // удаляем найденные точки чтоб потом не было ложных детектов
12.              search_neighbours(array, x, y, x_max, y_max);
13.           }
14.       }
15.    }
16.    return num_of_isles;
17. }
18.  
19. void search_neighbours(bool* array, int x, int y, int x_max, int y_max)
20. {
21.    if((array[x-1][y-1])&&(y>0)&&(x>0))
22.    {
23.       array[x-1][y-1]=false;
24.       search_neighbours(array, x-1, y-1, x_max, y_max);
25.    }
26.    if((array[x][y-1])&&(y>0))
27.    {
28.       array[x][y-1]=false;
29.       search_neighbours(array, x, y-1, x_max, y_max);
30.    }
31.    if((array[x+1][y-1])&&(y>0)&&(x<x_max))
32.    {
33.       array[x+1][y-1]=false;
34.       search_neighbours(array, x+1, y-1, x_max, y_max);
35.    }
36.    if((array[x-1][y])&&(x>0))
37.    {
38.       array[x-1][y]=false;
39.       search_neighbours(array, x-1, y, x_max, y_max);
40.    }
41.    if((array[x+1][y])&&(x<x_max))
42.    {
43.       array[x+1][y]=false;
44.       search_neighbours(array, x+1, y, x_max, y_max);
45.    }
46.    if((array[x-1][y+1])&&(y<y_max)&&(x>0))
47.    {
48.       array[x-1][y+1]=false;
49.       search_neighbours(array, x-1, y+1, x_max, y_max);
50.    }
51.    if((array[x][y+1])&&(y<y_max))
52.    {
53.       array[x][y+1]=false;
54.       search_neighbours(array, x, y+1, x_max, y_max);
55.    }
56.    if((array[x+1][y+1])&&(y<y_max)&&(x<x_max))
57.    {
58.       array[x+1][y+1]=false;
59.       search_neighbours(array, x+1, y+1, x_max, y_max);
60.    }
61. }

ред. немного поправил код

 

методом раскраски.
просматриваете карту построчно, при встрече нераскрашенного острова - раскрашиваете его в очередной цвет (обычный алгоритм заливки цветом). и так до конца карты. количество цветов в которые вы раскрасили == количество островов.

 

qqwe
дык я тоже самое предложил, только не знал что это "метод раскраски"

 

Метод раскраски годный, добавлю только что его можно распараллелить. Если разбить массив на горизонтальные или вертикальные сегменты и каждый поток запускать для своего сегмента. После нужно будет объединить цвета на стыках, сделать это можно дополнительным проходом в этих стыках. Для этого можно завести отдельный массив реальных цветов. Идём по стыку, видим что цвета объединились и записываем в их ячейки реальный цвет(любой из этих двух). Если объединяются цвета которые уже ранее были объединёнными, то придётся искать по-этому массиву, чтобы установить реальный цвет для всех уже ранее объединённых. Тут есть некоторый простор для оптимизации.