[10252] 그리드 그래프

https://www.acmicpc.net/problem/10252

10252번: 그리드 그래프

 

일단 (0, 0)에서 맨 윗줄과 맨 오른줄을 순회하고 시작한다.

행이 홀수라면 단순히 원형으로 연결된 간선을 밟지않고 지날 수 없으므로, 1회는 원형간선을 거쳐야한다.

(n-1, m-1)에서 (n-1, 0)으로 간 다음에는, 다시 인접한 간선만 밟아 올라갈 수 있다.

행이 짝수라면 더욱 간단히, 원형간선을 밟지 않아도 된다.

모든 과정에서, 지나가는 열의 번호는 행의 홀짝 여부에 따라 상향식 혹은 하향식이 된다.

 

---

#include <bits/stdc++.h>

using namespace std;

void print(int y, int x) { cout << "(" << y << "," << x << ")\n"; }

int main(void) {

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    int t;

    cin >> t;

    while (t--) {

        int n, m;

        cin >> n >> m;

        int i, j;

        cout << "1\n";

        for (i = 0; i < m; i++) print(0, i);

        for (i = 1; i < n; i++) print(i, m - 1);

        if (n & 1) {

            for (i = n - 1; i >= 1; i--) {

                if (!(i & 1))

                    for (j = 0; j <= m - 2; j++) print(i, j);

                else

                    for (j = m - 2; j >= 0; j--) print(i, j);

            }

        } else {

            for (i = n - 1; i >= 1; i--) {

                if (i & 1)

                    for (j = m - 2; j >= 0; j--) print(i, j);

                else

                    for (j = 0; j <= m - 2; j++) print(i, j);

            }

        }

    }

}

---