zerocold's blog

DFS Problem
By zerocold, 11 years ago, In English
  • hi everyone i need a help to solve this 308 UVA_Problem

http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=244

this is a problem on DFS algorithm but i am just learned this algorithm and start to solve on it in this problem i can't find any observation to solve it?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  1. Find all possible intersection points between segments
  2. Combile all intersection points and subsegments into rectangles
  3. Apply DFS to all the rectangles (two rectangles are "linked" in case of having at least one common segment or non-zero intersection square)
  4. As a result, you will get connected components count. Each connected components is equal to one hole.
→ Reply