ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Artur Mogozov                        2:5002/7.6     28 May 2003  11:45:07
 To : All
 Subject : Задача
 -------------------------------------------------------------------------------- 
 

  [ы] Привет, как жизнь, All ?
 
 Задача E. Путешествие фигуры. Ограничение по времени - 1 секунда на тест.
 
 Hа шахматной доске размером N x N стоит конь, который ходит по обычным
 шахматным правилам. Hадо найти самый короткий путь из исходной клетки в
 заданную. Hекоторые поля считаются запрещенными, на них фигуру ставить нельзя.
 Если путь не существует вообще, вывести сообщение об этом.
 
 Формат входного файла:
 
 Первая строка - число N (2 < N < 500) - размер шахматной доски
 
 Вторая строка - два числа через пробел - координаты клетки (номер горизонтали и
 номер вертикали), на которой стоит конь (горизонтали и вертикали пронумерованы
 от 1 до N, начиная с левого верхнего угла)
 
 Третья строка - два числа через пробел - координаты клетки, в которую должен
 попасть конь.
 
 Последующие строки также содержат по два числа через пробел - координаты
 <запрещенных> клеток.
 
 В последней строке файла содержится комбинация 0 0 - признак конца ввода
 
 Формат выходного файла:
 
 Первая строка - слово YES, если путь из исходной клетки в заданную существует,
 слово NO, если пути нет.
 
 Вторая строка (если путь существует) - длина (в клетках) самого короткого пути
 из исходной клетки в заданную. Исходная клетка не учитывается.
 
 Пример входного файла input.txt
 
 3
 1 3
 2 3
 2 2
 0 0
 
 Пример выходного файла output.txt
 
 YES
 3
 
 Какой здесь эхотаг? Задача с школьной олимпиады. Во время контеста никто даже
 сдавать ее не пытался. Есть у меня рекурсивное решение, но при таких
 ограничениях на N и на время, оно вряд-ли пройдет.
 
  [ы] Пока, All, счастливого тебе коннекта ! ...
 --- Accept - Breaking Up Again [now]
  * Origin: - Доктоp, я вчеpа Windows... - К ГИHЕКОЛОГУ! (2:5002/7.6)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Задача   Artur Mogozov   28 May 2003 11:45:07   Задача   Anton Tikhonov   28 May 2003 11:21:49   Задача   Sam   28 May 2003 14:23:22   Re: Задача   Andrew Ezhguroff   28 May 2003 14:24:54   Задача   Serge Nozhenko   28 May 2003 15:36:36   Задача   Mity Usanov   28 May 2003 23:05:03   Задача   Igor Bychkov   29 May 2003 00:29:11