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

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

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

    www Гость

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

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

    CodeSweeper Гость

    ... нифига себе какие у людей проблемы ....
     
  3. STYX

    STYX Гость

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

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

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

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

    STYX Гость

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

    HuMmmBug Гость

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

    Kernel Гость

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

    ASh Гость

    Найти минимальный путь из точки 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 Гость

    Упс.... похерило ident.

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

    STYX Гость

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

    Kernel Гость

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

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

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

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

    Guest Гость

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

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

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

    Kernel Гость

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

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

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