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

Графы. Помогите составить смежную матрицу.

StUV

StUV

Rotaredom
tristram
если немного подумать, то можно обнаружить интересную закономерность в разнице значений двух величин в любом выбранном направлении из 6-ти
анализ ессно надо начинать с первой вершины
дальше все просто =)
с помощью этой закономерности (лень все здесь расписывать) можно легко построить граф (матрицой смежности или списками см. вершин), а потом уже поиск по этому графу...

rotoZOOM
замэпить эту систему на декартовую можно, но
если только навтыкать пустых ячеек с расстояниями до них нулевой длины

-~{}~ 19.08.05 18:51:

зы: и опять же нумерацию этих пустых ячеек и соответствие их смежных с ними надо где-то хранить :)
 
StUV

StUV

Rotaredom
tristram
для начала посчитай количество вершин на каждом витке спирали
подумай над этим ...
 

SiMM

Новичок
> оно растет
"Нижняя левая диагональ" - 1, 7, 19, 37, 61 ... - неужели дальше ряд продолжить не в состоянии?
 
rotoZOOM

rotoZOOM

ACM maniac
StUV все это делается либо двумерной матрицей либо списком уже помещенных вершин.
Существует 5 направлений по которым надо идти (-1,1) (0,1) (1,0) (0,-1) (-1,-1).
Сначала в (0,0) ставим 1, затем ставим в (0,-1) 2,
затем у нас должно быть 2 вещи.
1. Текущее направление
2. Следующее направление
Алгоритм заполнения следующий:
идем по текущему направлению расставляя числа, как только доходим до того момента, что в Следующем направлении стоит свободная клетка, то Текущее направление становится Следующим направлением, а следующее становится (Следующим+1)%5;
после того, как мы поставили двойку Текущее направление у нас 0 (то есть (-1,1)), а Cледующее 1 (то есть (0,1))
Пример заполнения:
PHP: 
$mas=array();
$dx=array(-1,0,1,0,-1);
$dy=array(1,1,0,-1,-1);
$cnt=3;
$max=100;
$mas[0][0]=1;
$mas[0][-1]=2;
$x=0;
$y=-1;
$cur=0;
$nxt=1;
while ($cnt<=$max){
    if (!isset($mas[$x+$dx[$nxt]][$y+$dy[$nxt]])){
        $cur=$nxt;
        $nxt=($nxt+1)%5;
    }
    $x+=$dx[$cur];
    $y+=$dy[$cur];
    $mas[$x][$y]=$cnt++;
}
print_r($mas);
Теперь у нас в массиве $mas содержатся все цифры от 1 до $max в своих координатах.
Осталось в массиве найти начальную точку от которой надо искать и после этого с нее запустить волну.
 

tristram

Guest
rotoZOOM
сделай плиз. я тебе очень признателен. с меня пиво :)
 

tristram

Guest
svetasmirnova
у меня алгоритм далеко несовершенный получился :(
// ну а чё?
 
dvp

dvp

Новичок
Мне думается всё же формулу можно построить и не очень сложно.
Если выбрать систему координат так:
Ось X: SW-NE (из юго-запада - на северо-восток)
Ось Y: NW-SE

То количество шагов, для перехода из точки A(x1;y1) в точку B(x2;y2) будет вычисляться так:
PHP: 
function calculate_path_length($x1, $x2, $y1, $y2) {
  // предполагаем $x1, $x2, $y1, $y2 заведомо целыми числами
  $dx = $x1-$x2;
  $dy = $y1-$y2;
  $length = $dx+$dy; // декартово расстояние
  // а теперь сноска, на возможность идти по диагонали,
  // если обе координаты увеличиваются или уменьшаются   одновременно
  if (($dx>0) && ($dy>0))
    $length -= min($dx, $dy);
  elseif  (($dx<0) && ($dy<0))
    $length += max($dx, $dy);
  
  return $length;
}
p.s. главное выбрать координаты именно в ту сторону как я сказал, либо в обратную по обоим осям одновременно. Так считать удобнее

-~{}~ 20.08.05 03:49:

Прошу прощения ........ пока читал топик, уже забыл, что на входе всего 2 числа - номера элемента спирали
 

tristram

Guest
dvp
спасибо пригодится когда уже будет таблица координат.
 

tristram

Guest
прохожу квест это одно из финальных заданий
 
dvp

dvp

Новичок
можно не париться и заполнить-таки декартовую матрицу от 1 до max(A1, A2), а потом по приведённой выше формуле посчитать расстояние.
правда с ростом N время выполнения будет пропорционально возрастать
 

tristram

Guest
dvp
а сколько будет уходить на расчет расстояния между двумя произвольными номерами 1-10 000? примерно.
 
dvp

dvp

Новичок
не знаю сколько, но совсем не много ............... тем более какая разница, если посчитать это надо всего один раз
 

tristram

Guest
dvp
сорри я стормозил =) ведь и правда один раз. сделай плиз если можешь. я уже задолбался ;(
 
rotoZOOM

rotoZOOM

ACM maniac
tristram в созданном массиве (программа выше) ищешь одно из искомых (простите за тафтологию) чисел.
Далее зная ее координаты, помещаешь их и количество пройденых шагов (в данном случае 0) в очередь.
И помечаешь, что в этих координатах ты уже был.
Дальше идет цикл, пока в очереди не останется элементов.
1. Берешь из очереди текущий элемент (то есть координаты и количество пройденных шагов).
2. Пытаешься из этих координат пойти в 6 возможных сторон (-1,0) (-1,1) (0,1) (1,1) (1,0) (0,-1)
3. Если существует число в этих координатах и ты там не был, то помещаешь эти координаты и количество пройденных шагов до нее в очередь
4. Смотришь если это число искомое, то выход из цикла
5. идем на пункт 1.
Это я попытался словесно объяснить волну, надеюсь реализовать труда особого не составит.
 
Войдите или зарегистрируйтесь для ответа.
Сверху