krishan's blog

How can we solve http://www.spoj.com/problems/RIOI_2_3/?

By krishan, 9 years ago, In English

http://www.spoj.com/problems/RIOI_2_3/

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Multi-level bfs? One (dfs or bfs) to determine what unvisited bosses he can visit next. Another bfs to find least number of bosses to visit.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For every possible subset of bosses with dfs check if we can go from Start to End visiting only cells with bosses in this subset. Complexity is O(502·210)

→ Reply