문제
https://www.acmicpc.net/problem/10252
문제해설
m X n의 그리드가 주어진다.
이 그리드는 인접하는 점들과 이어져있고
각 행과 열의 마지막 점과 첫번째 점과도 연결되어있다.
이러한 그리드에서 모든 정점을 한번씩만 지나며
시작점으로 다시 돌아올 수 있는 사이클을 찾아 출력하면 된다.
문제풀이
이 문제는 짝수와 홀수로 나누어 생각해주면 된다.
행이 짝수일 경우에는
위 그림과 같은 순서로 방문해주면 된다.
행이 홀수라면
위 그림과 같은 순서로 방문해준다.
13번에서 14번으로 이동할 수 있는 것은
첫 점과 마지막점이 연결되어 있기 때문이다.
위 순서대로 방문해주며 각 위치를 출력해주면 된다.
해가 존재하지 않는 경우는 없다.
전체코드
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
#include<iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int t; cin >> t;
while (t--) {
int m, n; cin >> m >> n;
int i = 0, j = 0;
cout << "1\n";
while (true) {
cout << '(' << i << ',' << j << ")\n";
if (i % 2)
j--;
else
j++;
if (j >= n || j < 1) {
i++;
if (i % 2)
j--;
else
j++;
}
if (i == m)
break;
}
for (int i = m - 1; i > 0; i--)
cout << '(' << i << ',' <<"0)\n";
}
return 0;
}