помогите с задачей

  • Автор темы -
  • Дата начала
Статус
Закрыто для дальнейших ответов.

Гость
#1
Люди подскажите как решить следующую задачу:

Пусть дана логическая матрица MxN, описывающая лабиринт (true – стена, false- проход) и начальное положение человека в лабиринте (x,y). Необходим алгоритм поиска ОПТИМАЛЬНОГО варианта обхода ВСЕХ доступных клеток лабиринта.

Заранее спасибо!
 
B

Barmutik

Гость
#2
В общем идея не моя, я ее, кажется, в RU.HACKER видел, но очень кpасивая.

Итак:
Ставишь в исходную клеточу 0. Во все соседние доступные из нее - 1.
дальше пpосматpиваешь весь массив, и ставишь 2 во все клетки доступные из
клеток содеpжащих 1. Итд 3 во все клетки доступные из 2...
Если в клетке уже есть значение меньшее или pавное тому, котоpое надо туда
поставить, мы его туда не ставим(т.е. необходимо начальное заполнение массива,
скажем, значениями 65535). Условие окончания - когда при очередной итерации не
поставили ни одной цифры.

Не могу сказать что он будет максимально оптимальный (!!!).. но не рекурсивный и максимальное
число операций сравнения m * n.

Да надо просто открыть книжку по алгоритмам и посмотреть ... :)
 
Статус
Закрыто для дальнейших ответов.