[BOJ 15684] 사다리 조작

문제 출처 : https://www.acmicpc.net/problem/15684

#include <bits/stdc++.h>

using namespace std;

int N, M, H, l[35][15], ans=4;

bool chk() {

for (int i = 0; i < N - 1; i++) {

int ni = 0; int nj = i;

while (1) {

if (ni == H) {

if (nj == i) break;

else return false;

}

nj += l[ni][nj]; ni++;

}

}

return true;

}

void bt(int ni, int nj, int n){

if (chk()) {ans = min(ans, n); return;}

if (n == 3) return;

for (int i = ni; i < H; i++) {

for (int j = nj; j < N - 1; j++) {

if (l[i][j] == 0 && l[i][j + 1] != 1) {

l[i][j] = 1; l[i][j + 1] = -1;

if (j + 2 >= N) bt(i+1, 0, n + 1);

bt(i, j + 1, n + 1);

l[i][j] = 0; l[i][j + 1] = 0;

}

}

nj = 0;

}

}

int main() {

ios::sync_with_stdio(0); cin.tie(0); cin >> N >> M >> H; int a, b;

for (int i = 0; i < M; i++) {

cin >> a >> b; l[a-1][b-1] = 1; l[a-1][b] = -1;

}

bt(0, 0, 0);

cout << (ans>3?-1:ans);

return 0;

}