• Paranoid - курс по анонимности и безопасности в сети от команды codeby. Защита персональных данных, анонимность в сети интернет, настройка виртуальных машин, безопасная передача данных, анти форензика и еще много всего полезного. Подробнее ...

  • Мобильный клиент нашего форума для Android гаджетов доступен в Google Play Market по этой ссылке. Клиент можно скачать с нашего форума по этой ссылке. Последняя версия МК в нашем телеграм канале вот здесь

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

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

Guest

#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.

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