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

Тема в разделе "Свободное общение", создана пользователем -, 11 апр 2005.

Статус темы:
Закрыта.
  1. Гость

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

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

    Заранее спасибо!
     
  2. Barmutik

    Barmutik Гость

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

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

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

    Да надо просто открыть книжку по алгоритмам и посмотреть ... :)
     
Загрузка...
Похожие Темы - помогите задачей
  1. Jenyyy
    Ответов:
    0
    Просмотров:
    799
  2. likan
    Ответов:
    1
    Просмотров:
    1.073
  3. dog2552
    Ответов:
    2
    Просмотров:
    1.145
  4. viktor2014
    Ответов:
    0
    Просмотров:
    1.161
  5. Comoc
    Ответов:
    0
    Просмотров:
    930
Статус темы:
Закрыта.

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