Форум PHP программистов > Кратчайший путь на PHP

[ Поиск ] - [ Пользователи ] - [ Календарь ]

fusix

9.04.2011 - 03:06

Здравствуйте. Мне нужен код для нахождения кратчайшего пути от точки (х, у) к точке с выводом пути ввиде: 1,1; 1,2;1,3;2,3 и т.п. Зарание спасибо. У меня никаких идей...

Спустя 2 часа, 18 минут, 36 секунд (9.04.2011 - 04:25) kirik написал(а):

По диагонали нельзя ходить?

Спустя 8 минут, 47 секунд (9.04.2011 - 04:33) kirik написал(а):

Два решения:

1 только горизонталь и вертикаль (как в описании задачи)

$start = $pos = array(1,1);
$end = array(2,3);

$path = array($start);
while($pos != $end) {
     if ($pos[1] != $end[1]) {
          $pos[1]++;
     } elseif($pos[0] != $end[0]) {
          $pos[0]++;
     }
     $path[] = $pos;
}

print_r($path);
/*
Array
(
    [0] => Array
        (
            [0] => 1
            [1] => 1
        )

    [1] => Array
        (
            [0] => 1
            [1] => 2
        )

    [2] => Array
        (
            [0] => 1
            [1] => 3
        )

    [3] => Array
        (
            [0] => 2
            [1] => 3
        )

)
*/

2 с возможностью перемещения по диагонали

$start = $pos = array(1,1);
$end = array(2,3);

$path = array($start);
while($pos != $end) {
     if ($pos[1] != $end[1]) {
          $pos[1]++;
     }
     if($pos[0] != $end[0]) {
          $pos[0]++;
     }
     $path[] = $pos;
}

print_r($path);
/*
Array
(
    [0] => Array
        (
            [0] => 1
            [1] => 1
        )

    [1] => Array
        (
            [0] => 2
            [1] => 2
        )

    [2] => Array
        (
            [0] => 2
            [1] => 3
        )

)
*/

Спустя 4 часа, 52 минуты, 38 секунд (9.04.2011 - 09:26) fusix написал(а):

Цитата (kirik @ 9.04.2011 - 01:33)

Два решения:

1 только горизонталь и вертикаль (как в описании задачи)

$start = $pos = array(1,1);
$end = array(2,3);

$path = array($start);
while($pos != $end) {
     if ($pos[1] != $end[1]) {
          $pos[1]++;
     } elseif($pos[0] != $end[0]) {
          $pos[0]++;
     }
     $path[] = $pos;
}

print_r($path);
/*
Array
(
    [0] => Array
        (
            [0] => 1
            [1] => 1
        )

    [1] => Array
        (
            [0] => 1
            [1] => 2
        )

    [2] => Array
        (
            [0] => 1
            [1] => 3
        )

    [3] => Array
        (
            [0] => 2
            [1] => 3
        )

)
*/

2 с возможностью перемещения по диагонали

$start = $pos = array(1,1);
$end = array(2,3);

$path = array($start);
while($pos != $end) {
     if ($pos[1] != $end[1]) {
          $pos[1]++;
     }
     if($pos[0] != $end[0]) {
          $pos[0]++;
     }
     $path[] = $pos;
}

print_r($path);
/*
Array
(
    [0] => Array
        (
            [0] => 1
            [1] => 1
        )

    [1] => Array
        (
            [0] => 2
            [1] => 2
        )

    [2] => Array
        (
            [0] => 2
            [1] => 3
        )

)
*/

А с обходом препятствий возможно?

Спустя 10 часов, 25 минут, 32 секунды (9.04.2011 - 19:52) kirik написал(а):

fusix
Всё возможно, если только захотеть

Спустя 1 час, 53 секунды (9.04.2011 - 20:53) Mirexzpalich написал(а):

Блин... Стандартная олимпиадная задачка 11класса.... Инфы в нэте просто завались....

Спустя 1 час, 9 минут, 59 секунд (9.04.2011 - 22:03) inpost написал(а):

Mirexzpalich
Ты про обход преград? Интересненько, надо бы посмотреть.

Спустя 13 часов, 17 минут, 33 секунды (10.04.2011 - 11:20) Mirexzpalich написал(а):

Да да... В одинадцатом классе на олимпиаде по прогораммированию была точно такая задача....

Быстрый ответ:

Здесь расположена полная версия этой страницы.