C. 그리드 그래프

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

i) m이 짝수일 때,

ii) m이 홀수일 때,

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

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