Discussion @ 1073. Square Country @ Timus Online Judge

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

Posted by Bobur 25 Dec 2007 21:49

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

Posted by ENick(TNU) 20 Jun 2008 02:29

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

Read about BFS here.

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

Posted by VNTU Vitaly(Traning) 28 May 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???

Posted by [LG]_#\#@P$T[101]R 28 May 2009 18:07

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

Discussion of Problem 1073. Square Country