티스토리 뷰

ICPC/2014 인터넷예선

C. 그리드 그래프

전명우 2014. 10. 7. 17:57

문제에서 $m \times n$ 크기의 토로이드 그래프를 정의한다. 이 토로이드 그래프에서 해밀턴 회로를 찾는 것이 문제다. 문제 조건에서 $m, n \geq 3$ 이므로 모든 $m \times n$ 크기의 토로이드 그래프에서 해밀턴 회로가 존재함을 알 수 있다.


i) m이 짝수일 때,


ii) m이 홀수일 때,



위와 같이 이동하면 해밀턴 회로가 된다.


'ICPC > 2014 인터넷예선' 카테고리의 다른 글

G. Mutation  (0) 2014.10.08
E. Highway  (0) 2014.10.07
D. 헨리  (0) 2014.10.07
B. Driving License  (1) 2014.10.07
A. ACM 호텔  (0) 2014.10.07
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함