[15684] 사다리 조작

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

15684번: 사다리 조작

백트래킹으로 풀때, 사다리의 조작여부를 판별하는 부분은 하나의 열이 조작되지 않은 순간 바로 false를 return한다.

이전의 인덱스를 기억하여야, check()의 호출횟수를 더욱 줄일 수 있고

사다리를 작은 횟수부터 놓아야 check()가 true일때 바로 정답을 출력하고 exit()할 수 있다.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

int n, m, h;

bool a[35][35];

bool check(void) {

    for (int i = 1; i <= n; i++) {

        int cur = i;

        for (int j = 1; j <= h; j++) {

            if (a[cur - 1][j])

                cur--;

            else if (a[cur][j])

                cur++;

        }

        if (cur != i) return false;

    }

    return true;

}

void f(int mx, int d, int jj) {

    if (d == mx) {

        if (check()) {

            cout << mx;

            exit(0);

        }

        return;

    }

    int i, j;

    for (i = 1; i < n; i++) {

        for (j = jj; j <= h; j++) {

            if (a[i - 1][j] || a[i][j] || a[i + 1][j]) continue;

            a[i][j] = true;

            f(mx, d + 1, j);

            a[i][j] = false;

        }

    }

}

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n >> m >> h;

    int i;

    for (i = 0; i < m; i++) {

        int A, B;

        cin >> A >> B;

        a[B][A] = true;

    }

    for (i = 0; i <= 3; i++) f(i, 0, 1);

    cout << -1;

    return 0;

}

---