Меню
Что нового?

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

Чем-то напомнило задачи по обработке изображений, когда нужно например контур выделить, там тоже окном 3x3 или меньше шаришься и почти аналогично заменяешь) ну если порог только один конечно.
 
ну хоть понял что значит рекурсия. Всем спасибо за советы. Еще подскажите почему я обращаюсь к $array_t[$x][$y] получаю не конкретное число "1", а массив Array[1]?
 
Игорь Z написал(а):
Вот тут не пойму почему я обращаюсь к $array_t[$x][$y] получаю не конкретное число "1", а массив Array[1]?
Нажмите для раскрытия...
Потому, что механизм парсинга переменных внутри строк упрощенный. Обрати внимание на раскраску:
PHP: 
echo"Сам элемент равен: $array_t[$x][$y]<br />";
Он полагает, что [$y] не относится к $array_t. Когда используешь внутри литералов не простые переменные, то лучше всегда подсказывать парсеру, что ты имеешь в виду:
PHP: 
echo"Сам элемент равен: {$array_t[$x][$y]}<br />";
Без такого указания парсер разделил это так:
PHP: 
echo"Сам элемент равен: {$array_t[$x]}[{$y}]<br />";
 
MiksIr, вот код для прохода по одному блоку:
PHP: 
function matrix($x, $y)
{
    $array_t[$x][$y]=2;
    if ($array_t[$x+1][$y]==0) matrix($x+1,$y);
    if ($array_t[$x-1][$y]==0) matrix($x-1,$y);
    if ($array_t[$x][$y+1]==0) matrix($x,$y+1);
    if ($array_t[$x][$y-1]==0) matrix($x,$y-1);
};
Напиши это же циклом.
 
Ragazzo написал(а):
Чем-то напомнило задачи по обработке изображений, когда нужно например контур выделить, там тоже окном 3x3 или меньше шаришься и почти аналогично заменяешь) ну если порог только один конечно.
Нажмите для раскрытия...
да, мне тоже так и не понимаю че они там считают,..

Игорь Z проблема может оказаться на много сложнее... фигуры бывают замкнутые. не попади в безвозратную рекурсию.. если есть желание подгляжу дома как я это решал...
 
С. написал(а):
MiksIr, вот код для прохода по одному блоку:
PHP: 
function matrix($x, $y)
{
    $array_t[$x][$y]=2;
    if ($array_t[$x+1][$y]==0) matrix($x+1,$y);
    if ($array_t[$x-1][$y]==0) matrix($x-1,$y);
    if ($array_t[$x][$y+1]==0) matrix($x,$y+1);
    if ($array_t[$x][$y-1]==0) matrix($x,$y-1);
};
Напиши это же циклом.
Нажмите для раскрытия...
думаешь так? не уверен, но мне казалась что проверки должны быть или по или против часовой стрелки *сверху слева снизу справа* и помним последнее направление если последнее направление было врава, пойск снизу начинается, если вниз то слева и тд
нужно считать такие блоки.. у меня кателок уже не варит тут ограничение толщина в 1

Код: 
00000
01110
01111
 
Ну на, прям в твоем же стиле.

PHP: 
while(list($x,$y) = array_shift($buffer))
{
    $array_t[$x][$y]=2;
    if ($array_t[$x+1][$y]==0) $buffer[] = array($x+1,$y);
    if ($array_t[$x-1][$y]==0) $buffer[] = array($x-1,$y);
    if ($array_t[$x][$y+1]==0) $buffer[] = array($x,$y+1);
    if ($array_t[$x][$y-1]==0) $buffer[] = array($x,$y-1);
};
 
WMix написал(а):
да, мне тоже так и не понимаю че они там считают,..

Игорь Z проблема может оказаться на много сложнее... фигуры бывают замкнутые. не попади в безвозратную рекурсию.. если есть желание подгляжу дома как я это решал...
Нажмите для раскрытия...
Там значение точки заменяется с 0 на 2, так что замкнутые не должны проблем доставить
 
MiksIr написал(а):
Там значение точки заменяется с 0 на 2, так что замкнутые не должны проблем доставить
Нажмите для раскрытия...
тогда есть другая проблема, мы потеряем то что нашли и не сможем верниться обратно
Код: 
11100
10101
10001
обход идет сверху слева... найдя первый 0 путь делится на 2 направления... но мне подумать нужно... как я говорил тут толщина 1 и то что я сказал тоже не подходит
 
обрабатываемый элемент вне функции не сохраняется или его как-то неверно зписываю?
PHP: 
function matrix($x, $y)
{
	$array_t[$x][$y]=3;
...
	echo"<br />Элемент в конце функции:{$array_t[$x][$y]}<br/>";
};
....
....
if ($array_t[$x][$y]==1)
	{
		$blok_noley++;
		matrix($x,$y);
		echo"Элемент  после (вне) функции:{$array_t[$x][$y]}<br/>";
	}
Выводит
Элемент в конце функции:3
Элемент после (вне) функции:1
Нажмите для раскрытия...
Почему вне функции значение $array_t[$x][$y] не сохраняется (=3)?
 
Игорь Z
напиши полностью задачу как она в оригинале звучит... слишком мысли разбегаются... может все намного проще?
 
Игорь Z написал(а):
обрабатываемый элемент вне функции не сохраняется или его как-то неверно зписываю?
Почему вне функции значение $array_t[$x][$y] не сохраняется (=3)?
Нажмите для раскрытия...
Птому что согласно правилам языка РНР это совершенно разные переменные, находящиеся в разных зонах видимости.
 
С. написал(а):
Ты "забыл" код для получения дополнительной сущности $buffer.
Нажмите для раскрытия...
А ты забыл, что твою "matrix($x, $y)" кто-то должен первый раз вызвать. Прикинь, да. У тебя это будет matrix($x, $y), у меня $buffer = array( array($x, $y) );
Еще какие "сущности" из пальца высасывать будешь?
 
Все просто.
PHP: 
function dfs ($y,$x,&$array)
{
    if (!isset($array[$y][$x]) || $array[$y][$x]!=0) return;
    $array[$y][$x] = 2;
    dfs($y-1, $x, $array);
    dfs($y+1, $x, $array);
    dfs($y, $x-1, $array);
    dfs($y, $x+1, $array);
}

/// тут где-то определен массив $array
$num_blocks = 0 ;
for ($y = 0 ; $y < count($array) ; $y++)
    for ($x = 0 ; $x < count($array[$x]) ; $x++)
    {
        if ($array[$y][$x] == 0)
        {
            $num_blocks++;
            dfs($y, $x, $array);
        }
    }
 
WMix написал(а):
тогда есть другая проблема, мы потеряем то что нашли и не сможем верниться обратно
Код: 
11100
10101
10001
обход идет сверху слева... найдя первый 0 путь делится на 2 направления... но мне подумать нужно... как я говорил тут толщина 1 и то что я сказал тоже не подходит
Нажмите для раскрытия...
Задача выведенного яйца не стоит. Ты пока, извини конечно, но чушь несешь. Тут не нужна стратегия, тут есть давно известные алгоритмы, просто C. предлагает реализовать его рекурсией (dfs),
а Миксир в ширину через очередь (bfs), оба решения правильные и оба имеют одинаковую сложность.
 
а ну да... я все фигуру запомнить пытался... слишком сложно думаю... пора зявязывать с этими глобальными мыслями....
 
Войдите или зарегистрируйтесь для ответа.
Сверху