[Link] https://www.acmicpc.net/problem/15684
Not to make mistakes
–multiple ladder can be added in the same vertical line –dfs range!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cstring>
// #include <bits/stdc++.h>
using namespace std;
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i < n; i++)
#define fori(s, e) for(int i = s; i < e; i++)
#define endl "\n"
#define nulls '\0'
#define dkdk " "
int n, m, h;
vector<set<int>> link;
int ans;
bool all_end = false;
bool satisfy() {
for0(i, n) {
int pos = i;
for0(height, h) {
if(link[height].count(pos)) {
pos++;
} else if(pos > 0 && link[height].count(pos-1)) {
pos--;
}
}
if(pos != i) {
return false;
}
}
return true;
}
void select(int cur_cnt, int max_cnt, int s_idx, int s_height) {
if(cur_cnt == max_cnt) {
if(satisfy()) {
ans = max_cnt;
all_end = true;
}
return;
}
for(int height = s_height; height < h; height++) {
if(link[height].count(s_idx)) continue;
if(s_idx-1 >= 0 && link[height].count(s_idx-1)) continue;
if(s_idx+1 < n-1 && link[height].count(s_idx+1)) continue;
link[height].insert(s_idx);
if(height == h - 1) select(cur_cnt+1, max_cnt, s_idx+1, 0);
else select(cur_cnt + 1, max_cnt, s_idx, height + 1);
if(all_end) return;
link[height].erase(s_idx);
}
for(int i = s_idx + 1; i < n-1; i++) {
for(int height = 0; height < h; height++) {
if(link[height].count(i)) continue;
if(i-1 >= 0 && link[height].count(i-1)) continue;
if(i+1 < n-1 && link[height].count(i+1)) continue;
link[height].insert(i);
if(height == h - 1) select(cur_cnt+1, max_cnt, i+1, 0);
else select(cur_cnt + 1, max_cnt, i, height + 1);
if(all_end) return;
link[height].erase(i);
}
}
}
void solve() {
for0(i, 4) {
select(0, i, 0, 0);
if(all_end) return;
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("input.txt", "r", stdin);
cin >> n >> m >> h;
link.resize(h);
for0(i, m) {
int a, b; cin >> a >> b;
a--, b--;
link[a].insert(b);
}
solve();
cout << (all_end ? ans : -1);
return 0;
}