got the islands...but first we scan each element then also dfs for them if all are 1..then how it can be o(row*col)...plz explain me complexity ofr this
On Fri, Apr 26, 2013 at 2:07 PM, atul anand <[email protected]> wrote: > {*1*,* 1*, 0, 0, 0}, > {0, *1*, 0, 0, *1* > }, > {*1*, 0, 0, *1*, *1*}, > {0, 0, 0, 0, 0}, > {*1*, 0, *1*, 0, *1*} > > above different set of color represent different island.Simple DFS is used to > find all the island > > > > On Fri, Apr 26, 2013 at 3:11 AM, Don <[email protected]> wrote: > >> The complexity is still O(ROWS*COLS) because each location in the >> matrix will be visited once by the loop and once by DFS. Once a >> location has been visited by DFS, it is marked as visited and can't be >> visited again. >> Don >> >> On Apr 25, 5:11 pm, rahul sharma <[email protected]> wrote: >> > What will be complexity if all elements in matrix are 1.. >> > >> > when first dfs will call then all matrix will be scanned setting each >> > element to visited... >> > then again loop contiues to scan all the elements..plz explain >> > >> > On Thu, Apr 11, 2013 at 2:04 AM, rahul sharma <[email protected] >> >wrote: >> > >> > >> > >> > >> > >> > >> > >> > > {*1*,* 1*, 0, 0, 0}, >> > > {0, *1*, 0, 0, *1*}, >> > > {*1*, 0, 0, *1*, *1*}, >> > > {0, 0, 0, 0, 0}, >> > > {*1*, 0, *1*, 0, *1*} >> > >> > > Can anybody eplain how there are 5 islands in above matrix..thnx in >> advance >> > >> > > source:-http://www.geeksforgeeks.org/find-number-of-islands/ >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> For more options, visit https://groups.google.com/groups/opt_out. >> >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
