Преобразование матрицы

[FYBVFPFYBC]

Привет всем!
Есть матрица заданного размера. Во всех ячейках нули и единицы, сгенерированные случайно и неравномерно. Вероятность встретить единицу в ячейке - 10%. Смежные ячейки с единицами образуют комплексы из ячеек-единиц. Смежными ячейками считаются все ячейки вокруг данной ячейки, то есть: и с четырёх сторон относительно данной, и с четырёх углов (по диагонали).

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

Один из возможных вариантов комплекса из ячеек-единиц с максимальным числом этих ячеек (5) может выглядеть так:

000000
001000
000100
001100
010000
000000

Заранее спасибо за ваши идеи!

P.S. Начальное количество нулей и единиц в матрице сохранять не обязательно.

[LynXzp]

http://www.programmersforum.ru/showthread.php?t=34061

[FYBVFPFYBC]

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

http://www.programmersforum.ru/showthread.php?t=34061

И что, умник? Если нечего сказать - не тратил бы чужое время. Мне нужна идея, код писать я собираюсь сама. На google.com бы ещё отправил...

[intmain]

LynXzp
+2001000

[Sciv]

Ну первым пунктом - берем комплекс и по краям загоняем в него нули, поскольку это обязательное условие, то есть:

000000
0xxxx0
0xxxx0
0xxxx0
0xxxx0
000000

x - Это пока не установленные цифры

2) Создаем некий счетчик для выноса лишних единиц из комплекса так сказать "за скобку"

3) Считаем, сколько в комплексе ячеек-единиц, и если больше - увеличиваем счетчик и убираем лишние единицы. Если меньше и счетчик>0, то добавляем единицы любо до пяти штук, либо сколько можем (зависит от содержимого счетчика). Сам счетчик, соответственно, декрементируем

4) Повторяем по всем комплексам матрицы пункты 1-3

В итоге всего этого непотребства в матрице появятся комплексы с пятью единицами либо меньше пяти единиц (но не больше). Меньше может появиться тогда, когда счетчик=0, а единиц в комплексе<5 => переходим к следующему комплексу, оставляя текущий в таком виде, в каком он сейчас

5) Если счетчик >0 Повторяем проход по всем комплексам, проверяем - если единиц <5 - дополняем до 5, уменьшая счетчик.

За идею сойдет?

[FYBVFPFYBC]

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

Ну первым пунктом - берем комплекс и по краям загоняем в него нули, поскольку это обязательное условие, то есть:

000000
0xxxx0
0xxxx0
0xxxx0
0xxxx0
000000

x - Это пока не установленные цифры

2) Создаем некий счетчик для выноса лишних единиц из комплекса так сказать "за скобку"

3) Считаем, сколько в комплексе ячеек-единиц, и если больше - увеличиваем счетчик и убираем лишние единицы. Если меньше и счетчик>0, то добавляем единицы любо до пяти штук, либо сколько можем (зависит от содержимого счетчика). Сам счетчик, соответственно, декрементируем

4) Повторяем по всем комплексам матрицы пункты 1-3

В итоге всего этого непотребства в матрице появятся комплексы с пятью единицами либо меньше пяти единиц (но не больше). Меньше может появиться тогда, когда счетчик=0, а единиц в комплексе<5 => переходим к следующему комплексу, оставляя текущий в таком виде, в каком он сейчас

5) Если счетчик >0 Повторяем проход по всем комплексам, проверяем - если единиц <5 - дополняем до 5, уменьшая счетчик.

За идею сойдет?

Большое спасибо.