#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#define ll long long
using namespace std;
int N, M, H, ans=1e9;
pair<bool,bool> graph[35][35];
int cnt[35];
bool startGame()
{
for(int i=1;i<=N;i++)
{
int loc = i;
for(int j=1;j<=H;j++)
{
auto cur = graph[j][loc];
if(cur.first){
loc--;
}else if(cur.second){
loc++;
}
}
if(loc != i) return false;
}
return true;
}
void DFS(int depth, int curH){
if(depth == 4)
{
return;
}
for(int i=curH;i<=H;i++)
{
for(int j=1;j<=N;j++)
{
auto cur = graph[i][j];
auto prev = graph[i][j-1];
auto next = graph[i][j+1];
if(cur.first or cur.second) continue;
if(!cur.second and !next.second and !cur.first){
graph[i][j].second = true;
graph[i][j+1].first = true;
if(startGame()) {
ans = min(ans,depth);
graph[i][j].second = false;
graph[i][j+1].first = false;
goto stop;
}
DFS(depth+1, i);
graph[i][j].second = false;
graph[i][j+1].first = false;
}
}
}
stop:;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M >> H;
for(int i=0;i<M;i++)
{
int a,b;
cin >> a >> b;
graph[a][b].second = true;
if(b+1 <=N)
graph[a][b+1].first = true;
}
if(startGame())
{
cout << 0;
return 0;
}
DFS(1,1);
if(ans == 1e9) ans = -1;
cout << ans;
return 0;
}
- 로직
최대 3-depth 백트래킹
을 통해 사다리를 놓는 경우
를 찾는다
starGame()
--> 사다리게임
을 하여 하나
라도 자신이 아니면
바로 return false
- 오래걸린 이유
- 해당 문제는 총
300개중 3개를 골라서 사다리를 놓는 경우의 수 (300C3)
라서 450만개
정도가 나와서 충분히 시간안에 해결이 가능
하다
- 나는
모든 세로축
에서 왼쪽 / 오른쪽 모두 사다리를 놓는 경우
를 검사
함
--> 한쪽만 하면 되는데
양쪽 모두 해서
중복이 많이 발생
해서 시간초과
가 났음