Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 19.10.2009, 21:52
Новичок

Отправить личное сообщение для zho-zig Посмотреть профиль Найти все сообщения от zho-zig
 
Регистрация: 19.10.2009
Сообщений: 7

Нужна помощь
Помогите решить задачу. Очень интересно посмотреть как она решается. Спасибо

Объезд королевства
ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 65536 KB.
ввод: input.txt
вывод: output.txt


Король шахматной доски размером 5х5 находится на коне в одной из клеток своего королевства. Он решил объехать все свое владение, но никуда не заезжая дважды, т.е. побывать в каждой клетке ровно по одному разу (наш король всегда путешествует на коне).
Вам предстоит выяснить для него маршрут или выяснить, что такого не существует.

Входные данные
Во входном файле содержится индекс клетки, в которой находится король (доска прономерована от 'A' до 'E' слева направо и от 1 до 5 снизу вверх).

Выходные данные
В выходной файл необходимо вывести маршрут короля без пробелов в том же формате или число 0, если маршрута не существует.

Пример

Ввод

A1

Вывод

A1C2E1D3B2D1E3D5B4A2C1E2C3A4C5E4D2B1A3B5D4B3A5C4E5
  #2  
Старый 19.10.2009, 23:26
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Ну наверно, задачу поиска замкнутого маршрута (гамильтонова цикла) коня на небольшой (шахматной) доске каждый программист должен сам решить хоть раз в жизни.
  #3  
Старый 20.10.2009, 00:30
гость

 
Сообщений: n/a

Есть алгоритм Варнсдорфа вроде, точно не помню, вообщем всегда идти в ту клетку, из которой меньше всего возможных ходов)
  #4  
Старый 20.10.2009, 07:29
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

мда, что-то вчера ветку не закрыл...

Название должно быть осмысленнным.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Размещения - Нужна помощь! MaxFlow Математические алгоритмы 6 25.02.2010 15:27
Программы на C++, нужна помощь starcode Реализация, исходники, языки 4 14.08.2009 18:29
Нужна помощь по ассемблеру! jekahm Реализация, исходники, языки 2 10.06.2009 14:33
нужна помощь гость Работа 0 13.05.2009 01:19
нужна помощь cheater_Ok Реализация, исходники, языки 5 15.03.2008 16:49