задача про озеро

Тема в разделе "Свободное общение", создана пользователем www, 24 мар 2004.

Статус темы:
Закрыта.
  1. www

    www Гость

    Репутация:
    0
    Помогите решить задачку!!!
    квадратное озеро задается матрицей М*Н и покрыто мелкими островками. в левом верхнем углу находится плот размером м*м. за один шаг плот может двигаться на одну клетку по вертиккали или горизонтали.
    требуется определить кратчайший путь плота до правого нижнего угла.

    задача для плота еденичного размера решается легко, а вот для квадратного не знаю как!.
     
  2. CodeSweeper

    CodeSweeper Гость

    Репутация:
    0
    ... нифига себе какие у людей проблемы ....
     
  3. STYX

    STYX Гость

    Репутация:
    0
    Очень нечетко сформулирована задача:

    Если оно квадратное, то зачем задавать две переменные: M*M.

    Т.е. площадь одной клетки равна площади плота?

    Тогда решение:
    (2M/m-1)m=X
     
  4. STYX

    STYX Гость

    Репутация:
    0
    Кстати, пока я не заметил, что все квадратное, я решал как будто прямоугольное: там два пути решения.
     
  5. HuMmmBug

    HuMmmBug Гость

    Репутация:
    0
    решение задачи по кратчайшему пути из точки в точку можно заделать на основе бинарных деревьев.
     
  6. Kernel

    Kernel Гость

    Репутация:
    0
    Ну и в чем прикол? Тот же поиск в ширину как и с плотом 1х1 только проверка прохождения чуть шире ... хранишь допустим как признак состояния координату левого верхнего угла ... ну то есть помечаешь точку как посещёённую если в ней стоит левый верхний угол плота, и при проверке посещения проверяеш её же ... или проблема в просчёте возможности прохождения плота?
     
  7. ASh

    ASh Гость

    Репутация:
    0
    Найти минимальный путь из точки A в точку B

    Пусть Bij есть длина пути из точки A в точку ij
    Pij есть предыдущие координаты плота перед попаданием в точку ij

    Python-like:

    Пока очередь не пуста
    Достаём очередные координаты плота
    Для всех клеток на которых "лежит" плот
    Если текущая длина пути + 1 < Bij то
    Bij = текущая длина пути + 1
    Pij = координаты_плота
    Добавляем обновлённые координаты в очередь

    Путь в конце алгоритма получаем "раскручиванием" P

    В принципе это модифицированный алгоритм Дейкстры.

    P.S. Сильно порадовало решение "гуру" STYX ;) (2M/m-1)m=X ;) :D :D :D :D :D
     
  8. ASh

    ASh Гость

    Репутация:
    0
    Упс.... похерило ident.

    И ещё не забываем двигать плот во всех направлениях как забыл я ;)
     
  9. STYX

    STYX Гость

    Репутация:
    0
    А что не так?! Извини, если что не понял, но как я писал слишком много неясного.
     
  10. Kernel

    Kernel Гость

    Репутация:
    0
    это с таким же успехом можно считать модифицированным алгоритмом Windows, изменений по крайней мере придётся вносить столько же как и в дейкстру (удалить всё и написать поиск в ширину который ты и описал) :D

    Ворос был в сложности реализации под плот неединичной ширины, и как сказал автор для плота единичного размера (этот самый поиск) у него проблем нет.
    STYX
    представь себе выложенный из островков лабиринт:
    _____
    ****_
    _____
    _****
    _____

    где _ это вода а * это островок. путь составит 16 единиц(если не считать стартовую точку)

    а по вышеописанной формуле вообще длинна пути для плота размером 1 равна бесконечности ;)
     
  11. Guest

    Guest Гость

    Репутация:
    0
    2Kernel,
    Вы категорически неправы! А если я скажу что это В ТОЧНОСТИ АЛГОРИТМ ДЕЙКСТРЫ?
    Вы мне поверите? Если нет, то в сад!

    Разворачиваем наше поле в граф и вуаля! Получаем в точности алгоритм дейкстры!

    P.S. чем поиск в ширину отличается от алгоритма Дейкстры?
     
  12. Kernel

    Kernel Гость

    Репутация:
    0
    1. Алгоритм дейкстры работает на графах со взвешенными рёбрами. (я конечно понимаю что "везде 1" это тоже по сути взвешенные рёбра)
    2. в алгоритме дейкстры вершина источника релаксации выбирается по минимум расстояния
    3. не путайте пожалуйста непосредсвенный поиск с кластеризуемым поиском, который и работает обычно по дейкстре ... хотя обычно он просто не работает :)

    ЗЫ: я конечно понимаю что любой алгоритм по поиску расстояния можно за уши притянуть к дейкстре (построили граф и понеслась) но как ни странно ни лучше, ни проще от этого не станет, а выч. сложность скорее всего вообще увеличится.
    Да и число вершин в таком графе будет M*M - соответсвенно матрица путей для графа M*M*M*M - что вообщем-то скорее всего будет не очень приятно.
     
Загрузка...
Статус темы:
Закрыта.

Поделиться этой страницей