ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1096. Таблички с номерами маршрутов

Let me tell you why you are wrong!!!
Послано 737363395 17 фев 2013 21:00
In this problem,many people use the BFS(breadth first search).However,you can't search it from the two numbers which are in the last line,you should search it from the plate you need.Because of this,I was wrong before at test#6.

If your can't understand it,you can test the sample input,the right answer is-
2
1
2
but not 2
4
2

And pay attention at the number of routes-1 to 2000.

Believe me!!!

Sorry to my English...I'm a Chinese...

Good luck to you.:)
Re: Let me tell you why you are wrong!!!
Послано 0909100811 19 фев 2013 15:13
=。= Why you say that? You should say "Sorry to my English...I'm a Japanese..."
Re: Let me tell you why you are wrong!!!
Послано Rabbit Girl ♥ 13 мар 2018 16:17
I ACed it with BFS first try! It took me 15 minutes to solve :\ What are you talking about?

~~~MY SOLUTION STAT~~~
Points nullified :
1) BFS doesn't work!
2) You can't search from the starting point.
3) Right answer isn't
   2
   4
   2
Additional points : INCONSISTENCY NULLIFICATION : 0 corresponds to YOUR plate!
Hope I made your "advice" invalid.

The key point is to build the graph (I did in K^2) and traverse it with BFS, so that you could find the SHORTEST path (K). That gives me O(K^2) in total.

Edited by author 13.03.2018 18:05