Блог пользователя zerocold

DFS Problem
Автор zerocold, 11 лет назад, По-английски
  • 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?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  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.
→ Ответить