2873 - 롤러코스터

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

홀수x짝수, 짝수x홀수, 홀수x홀수 크기에 대해서는 모든 경로를 방문하여 가장 오른쪽 아래 칸으로 갈 수 있다.

짝수x짝수 크기는 1칸 빼고 나머지는 다 방문해서 도착할 수 있는데, (홀수, 짝수) 또는 (짝수, 홀수)에 위치한 칸을 들리지 못한다. 빼는 1칸은 가장 작은 기쁨이 있는 칸을 선택하면 될 것이다.

여기까지는 어떻게 생각해냈는데, 경로를 어떻게 만들어야할지 몰라서 한참 고민하다 결국 솔루션을 참고해버렸다.

경로를 크게 3부분으로 나눈다.

가운데 지그재그로 제외할 1칸을 피해서 이동하는 것 때문이다. 지그재그로 2줄만 어떻게 해결하면 되므로, 그 전행까지는 R...RDL...LD 로 이동하고, 이후의 행부터는 DL...LDR...R 로 이동하면 된다.

#include <cstdio>
using namespace std;

int H, W;
int a[1000][1000];

void repeat(char ch, int repeated){while(repeated-->0)putchar(ch);}

int main(){
    scanf("%d %d", &H, &W);
    
    for(int i=0; i<H; ++i){
        for(int j=0; j<W; ++j){
            scanf("%d", &a[i][j]);
        }
    }
    
    if( H%2 ){
        repeat('R', W-1);
        for(int i=0; i<H-1; i+=2){
            repeat('D', 1); repeat('L', W-1);
            repeat('D', 1); repeat('R', W-1);
        }
    } else if( W%2 ){
        repeat('D', H-1);
        for(int i=0; i<W-1; i+=2){
            repeat('R', 1); repeat('U', H-1);
            repeat('R', 1); repeat('D', H-1);
        }
    } else {
        // finding minimum cell
        int x=0, y=1;
        for(int i=0; i<H; ++i){
            for(int j=0; j<W; ++j){
                if((i+j)%2 && a[y][x] > a[i][j]){
                    y = i, x = j;
                }
            }
        }
    
        int h=0, w=0;
        // top
        for(; h+1 < y; h += 2){
            repeat('R', W-1); repeat('D', 1);
            repeat('L', W-1); repeat('D', 1);
        }
        
        // middle
        int ny = h^1;
        for(w=0; w < W-1; ++w){
            if( ny != y || w != x ){
                repeat( ny%2 ? 'D':'U', 1);
                ny ^= 1;
            }
            repeat('R', 1);
        }
        if( ny%2 ) repeat('D', 1);
        
        // bottom
        h = (h/2*2) + 2;
        for(; h < H; h += 2){
            repeat('D', 1); repeat('L', W-1);
            repeat('D', 1); repeat('R', W-1);
        }
    }
    
    return 0;
}