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

  • Автор темы www
  • Дата начала
Статус
Закрыто для дальнейших ответов.
W
#1
Помогите решить задачку!!!
квадратное озеро задается матрицей М*Н и покрыто мелкими островками. в левом верхнем углу находится плот размером м*м. за один шаг плот может двигаться на одну клетку по вертиккали или горизонтали.
требуется определить кратчайший путь плота до правого нижнего угла.

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

STYX

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

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

в левом верхнем углу находится плот размером м*м. за один шаг плот может двигаться на одну клетку
Т.е. площадь одной клетки равна площади плота?

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

STYX

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

HuMmmBug

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

Kernel

#6
Ну и в чем прикол? Тот же поиск в ширину как и с плотом 1х1 только проверка прохождения чуть шире ... хранишь допустим как признак состояния координату левого верхнего угла ... ну то есть помечаешь точку как посещёённую если в ней стоит левый верхний угол плота, и при проверке посещения проверяеш её же ... или проблема в просчёте возможности прохождения плота?
 
A
#7
Найти минимальный путь из точки 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
 
A
#8
Упс.... похерило ident.

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

Kernel

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

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

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

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

Guest

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

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

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

Kernel

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

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