J. Tours

문제에서 toroidal triangular lattices와 toroidal hexagonal lattices에 대해 그림 예시가 있다. Triangular lattices는 $M$이 짝수이며, hexagonal lattices는 $M$, $N$ 둘 다 짝수란 조건이 있다. 이런 그래프에서 해밀턴 회로 중 임의의 하나를 찾는 문제다.

이 문제는 2014 인터넷예선 그리드 그래프 문제와 흡사하다. 아래와 같은 방법으로 정점 순회를 하면 해밀턴 회로가 된다.

   

#include <stdio.h> int T, M, N, P; int main() { int i, j; for (scanf("%d", &T);T--;){ scanf("%d%d%d", &M, &N, &P); puts("1"); if (P == 3){ for (i=0;i<M;i++){ if (i&1) for (j=N;j--;) printf("(%d,%d)\n", i, j); else for (j=0;j<N;j++) printf("(%d,%d)\n", i, j); } } else{ for (j=0;j<N;j++){ if (j&1) for (i=0;i<M;i++) printf("(%d,%d)\n", i, j); else for (i=M;i--;) printf("(%d,%d)\n", i, j); } } } }