15684 사다리 조작

백트래킹 문제다. 근데 삐끗하면 시간초과나기 쉽다.

약간의 꼼수인데 0번~3번까지 순서대로 검사하면서 결과 나오는 순간 출력하는 방식이다.

#include <stdio.h>
 
int n, m, h, ans;
char lines[31][11];
char s[5][11];
 
void swap(char &a, char &b) {
    char temp = a;
    a = b;
    b = temp;
}
 
void dfs(int depth, int pos, int cnt, int d) {
    if (ans) return;
    for (int i = 0; i <= n; i++) s[d][i] = s[d + 1][i];
    for (int i = depth; i <= h; i++) {
        for (int j = pos; j < n; j++) {
            if (lines[i][j]) swap(s[d][j], s[d][j + 1]);
            if (lines[i][j - 1] | lines[i][j] | lines[i][j + 1] || !cnt) continue;
            lines[i][j] = 1; swap(s[d][j], s[d][j + 1]);
            dfs(i, j + 1, cnt - 1, d - 1);
            lines[i][j] = 0; swap(s[d][j], s[d][j + 1]);
            if (ans) 
                return;
        }
        pos = 1;
    }
    bool f = true;
    for (int i = 1; i <= n; i++) if (s[d][i] != i) {
        f = false;
        return;
    }
    ans = f;
}
 
int main() {
    scanf("%d%d%d", &n, &m, &h);
    while (m--) {
        int u, v;
        scanf("%d%d", &u, &v);
        lines[u][v] = 1;
    }
    for (int i = 0; i < 4; i++) {
        for (int j = 1; j <= n; j++) s[4][j] = j;
        dfs(1, 1, i, 3);
        if(ans) {
            printf("%d\n", i);
            return 0;
        }
    }
    printf("-1");
    return 0;
}