не могу придумать алгоритм решения (матрицы)

[Игорь Z]

есть матрица NхN из 0 и 1.
Как бы мне при переборе при нахождении 0 изменить его на 2 и изменить всех его соседей нолей на 2 и соседей нолей этих найденых соседей...
Например:
Вот матрица N=10:
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 0 0 0 1
1 1 1 1 1 1 1 1 0 1
1 0 0 0 0 1 1 1 0 1
1 0 1 1 0 1 0 1 0 1
1 0 1 1 0 1 0 1 0 1
1 0 1 1 0 1 1 1 0 1
1 0 1 1 1 1 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 0
Как мне при переборе элементов как только элемент=0 (у меня array[1][5]) изменить этот и все соседние элементы и их соседей...как на картинке желтым цветом изменить на 2.

 

[С.]

При такой формулировке задачи достаточно просто тупо заменить ВСЕ нули на двойки.

 

[Игорь Z]

При такой формулировке задачи достаточно просто тупо заменить ВСЕ нули на двойки.

тогда я не смогу посчитать отдельно количество измененных блоков ($blok_nolei++). На рисунке там их ТРИ.

 

[Игорь Z]

вот перебираю массив дохожу до array[1][5] - он ноль значит $blok_nolei++ и его и всех соседей меняю на 2 (или на 1)...
тут же смотю array[1][5+1], array[1][5-1], array[1+1][5] и array[1-1][5] и если они =0 то (меняю их на 2 и проверяю их соседей) и так дальше...
Но как этот алгоритм представить - не пойму...

 

[С.]

Надо формулировки корректные давать.

Обходишь все ячейки. Если встречаешь ноль, проверяешь всех его соседей. Если ни одной двойки нет, то $blok_nolei++. Заменяешь рассматриваемый нуль на двойку. Пошел на следующую ячейку.

 

[Игорь Z]

Но тогда когда я дойду до элемента array[3][1] - он ноль и соседей "2" нет и нужно ставить $blok_nolei++, а ведь он из того же блока, который уже найден и посчитан...

 

[Игорь Z]

может еще и проверять
если элемент = 2 и сосед есть тоже 2 то $blok_nolei--; ?

 

[С.]

Да действительно. Думал можно будет без рекурсии обойтись. Тогда с ней родимой. Рекурсивно заменешь всех нулевых соседей.

 

[Игорь Z]

Да действительно. Думал можно будет без рекурсии обойтись. Тогда с ней родимой. Рекурсивно заменешь всех нулевых соседей.

вот бы еще понимать значение слова "рекурсивно"...

 

[С.]

Подготавливаешь функцию F($x,$y), делающую обработку одного шага. В нее входит замене 0 на 2 и перебор соседей. При встрече соседнего нуля, применяешь к нeму ту же функцию F($x2,$y2).

Потом просто обходишь все ячейки по порядку и к нулевым применяешь эту функцию. Сколько нулей встретишь, столько и блоков.

 

[craz]

главное не забудь выходить из этой функции. С. не написал этого.

 

[С.]

craz, как можно забыть выйти из функции?

 

[craz]

из рекурсивной? не принужденно и легко

 

[С.]

Ладно, ясно с тобой, непринужденный ты наш.

 

[Игорь Z]

При встрече соседнего нуля, применяешь к нeму ту же функцию F($x2,$y2)

Как это понять? При встрече 0 в фунции вызываю ту же функцию?

function matrix($x, $y)
	{
         $blok_nolei++;
	$array_t[$x][$y]=2;
	if ($array_t[$x+1][$y]==0) { $array_t[$x+1][$y]=2; matrix($x+1,$y);}
	if ($array_t[$x-1][$y]==0){$array_t[$x-1][$y]=2; matrix($x-1,$y);}
	if ($array_t[$x][$y+1]==0){$array_t[$x][$y+1]=2; matrix($x,$y+1);}
	if ($array_t[$x][$y-1]==0){$array_t[$x][$y+1]=2; matrix($x,$y-1);}
	};

Я верно понял - внутри функции можно вызвать ту-же функцию?

 

[MiksIr]

Очень часто рекурсию можно заменить на цикл. Что удобнее и легче в отладке.
Основной цикл
-- Ловишь ноль, число блоков ++, функция заполнения с координатами нуля
---- у функции исходный массив пока с одним параметром - переданными координатами
---- идем циклом по этому массиву до тех пор, пока там есть элементы (координаты)
------ заполняем текущую координату двойкой, смотрим соседей, добавляем все соседи-нули в массив
---- конец цикла
-- конец функции
конец основного цикла

 

[С.]

MiksIr, Цикл никогда не был и не будет удобнее и легче в такого рода задачах. Менее ресурсоемок -- да, но не удобнее. Не стоит здесь блистать своей эрудицей, сбивая с толку новичка.

Игорь Z, вызов функции внутри самой себя и называется рекурсия. Скелет набросан правильно. Только зачем ты присваиваешь 2-ку соседям? Ты же вызываешь функцию для соседа, а она сама уже присвоет эту двойку.

Да, и счет блоков не в функции происходит, я такого не писал.

 

[Игорь Z]

как-то не могу обратится к элементу массива.

echo"<br />Масссив ДО:<br />";
		print_r ($array_t[$x]);
		echo"вызываю матрикс(х=$x у=$y)<br />";
		echo"Сам элемент равен: $array_t[$x][$y]<br />";

Результат:

Масссив ДО:
Array ( [0] => 2 [1] => 1 [2] => 2 ) вызываю матрикс(х=0 у=1)
Сам элемент равен: Array[1]
1

Вот тут не пойму почему я обращаюсь к $array_t[$x][$y] получаю не конкретное число "1", а массив Array[1]?

 

[MiksIr]

С., Рекурсия никогда не была и не будет удобнее и легче в такого рода задачах. Не стоит здесь блистать своей эрудицей, сбивая с толку новичка.

 

[MiksIr]

как-то не могу обратится к элементу массива.

Почитайте этот раздел
http://php.net/manual/ru/language.types.string.php#language.types.string.parsing