Обсуждение @ 1073. Квадратная страна @ Timus Online Judge

i can't understand BFS, what is it???

Послано Bobur 25 дек 2007 21:49

Re: i can't understand BFS, what is it???

Послано ENick(TNU) 20 июн 2008 02:29

http://www.intuit.ru/department/algorithms/gaa/4/

Read about BFS here.

Re: i can't understand BFS, what is it???

Послано VNTU Vitaly(Traning) 28 май 2009 14:28

Let image graph where every number is vertex, then we can add edge from a to b if a+SQ=b (where SQ - some square). Now you can see graph, there maximum 60000 vertex and maximum ~ 60000*300 = 18 000 000 edges, out task is find way from 0 to given number. BFS will done this in O(N+M)

Re: i can't understand BFS, what is it???

Послано [LG]_#\#@P$T[101]R 28 май 2009 18:07

this task is easy to solve O(N) time ;)

Обсуждение задачи 1073. Квадратная страна