1. Набираем команду codeby webinar. Набираем команду для организации и проведения вебинаров. Подробнее ...

    Скрыть объявление
  2. Требуются разработчики и тестеры для проекта codebyOS. Требования для участия в проекте: Знание принципов работы ОС на базе Linux; Знание Bash; Крайне желательное знание CPP, Python, Lua; Навыки системного администрирования. Подробнее ...

    Скрыть объявление
  3. Получи 30.000 рублей. Для получения денег необходимо принять участие в конкурсе авторов codeby. С условиями и призами можно ознакомиться на этой странице ...

    Внимание! Регистрация авторов на конкурс закрыта.

    Скрыть объявление

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

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

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

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

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

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

    Barmutik Гость

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

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

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

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

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