2873번: 롤러코스터

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


$O(rc)$

r,c 둘 중 하나가 홀수이면 지그재그로 돌아 모든 칸을 탐색할 수 있다.
문제는 r,c 둘다 짝수 일 때인데, 이 경우 (짝,홀) 혹은 (홀,짝)인 지점 하나를 제외하고 모두 돌 수 있다.(그러므로 가치가 최소인 지점을 제외하면 될 것이다.)
이를 증명하는건 어렵지 않다.
모든 지점은 A={(짝,짝),(홀,홀)} / B={(짝,홀),(홀,짝)} 두 집합 중 하나에 포함된다.
시작 지점과 도착 지점은 A 집합에 포함된다.
그런데 탐색할 때 A, B 집합의 한 지점을 번갈아 이루어지므로 탐색을 마친 후 들른 지점 수를 비교하면 B집합이 A집합보다 하나 작다는 결론을 내릴 수 있다.
즉, B 집합 중 하나의 지점을 제외하고 나머지 모든 지점을 탐색할 수 있는 일반적인 방법을 제시하면 된다.
이 방법을 찾는 것은 그리 어렵지 않으니 알아서 찾아 보도록 하자.

#include<cstdio>
int r, c, a[1000][1000];
void f(int sx, int sy, int ex, int ey, int t) {
    if (t & 1) {
        for (int i = sy; i <= ey; i++) {
            for (int j = sx; j < ex; j++) printf("%c", i - sx + t / 2 & 1 ? 'U' : 'D');
            if (i^ey) printf("R");
        }
    }
    else {
        for (int i = sx; i <= ex; i++) {
            for (int j = sy; j < ey; j++) printf("%c", i - sy + t / 2 & 1 ? 'L' : 'R');
            if (i^ex) printf("D");
        }
    }
}
int main() {
    scanf("%d %d", &r, &c);
    int mini = 1e9, tx, ty;
    for (int i = 0; i < r; i++) for (int j = 0; j < c; j++) {
        scanf("%d", &a[i][j]);
        if (i + j & 1 && a[i][j] < mini) {
            mini = a[i][j];
            tx = i;
            ty = j;
        }
    }
    if (r & 1) f(0, 0, r - 1, c - 1, 0);
    else if (c & 1) f(0, 0, r - 1, c - 1, 1);
    else {
        int bx = tx / 2 * 2, by = ty / 2 * 2;
        if (0 < by) f(0, 0, bx + 1, by - 1, 1), printf("R");
        if (0 < bx)f(0, by, bx - 1, by + 1, 0), printf("D");
        printf(tx & 1 ? "RD" : "DR");
        if (by < c - 2) printf("R"), f(0, by + 2, bx + 1, c - 1, 3);
        if (bx < r - 2) printf("D"), f(bx + 2, 0, r - 1, c - 1, 2);
    }
    return 0;
}