[백준 15684] 사다리 조작 (조합) (C/C++) (★★★)

#include <stdio.h>
#include <iostream>
using namespace std;
 
int visited[35][15];
int row, col, num;
int flag;
int Min = 9999999;
 
pair<int, int> candidate[400];
int candidateCnt;
 
int check()
{
    for(int i = 1; i <= col; i++)
    {
        int x = 1;
        int y = i;
        
        while(1)
        {
            if(visited[x][y] == 0 && visited[x][y-1] == 0)
            {
                x++;
            }
            else if(visited[x][y] == 1)
            {
                x++;
                y++;
            }
            else if(visited[x][y-1] == 1)
            {
                x++;
                y--;
            }
            
            if(x == row+1)
            {
                break;
            }
        }
        
        if(y != i)
        {
            return 0;
        }
    }    
    
    return 1;
}
 
void combination(int idx, int cnt)
{
    if(cnt > 3)
    {
        return;
    }
    
    if(check() == 1)
    {
        if(cnt < Min)
        {
            Min = cnt;
        }
        
        return;
    }
    
    for(int i = idx; i < candidateCnt; i++)
    {
        int x = candidate[i].first;
        int y = candidate[i].second;
        
        if(visited[x][y-1] == 1 || visited[x][y+1] == 1 || visited[x][y] == 1)
        {
            continue;
        }
        else
        {
            visited[x][y] = 1;
            combination(i+1, cnt+1);
            visited[x][y] = 0;
        }
    }
}
 
int main(void)
{
//    freopen("B15684_input.txt", "r", stdin);
    
    scanf("%d %d %d", &col, &num, &row);
    
    for(int i = 1; i <= num; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        visited[a][b] = 1;
    }
    
    for(int i = 1; i <= row; i++)
    {
        for(int j = 1; j <= col; j++)
        {
            if(visited[i][j] == 0)
            {
                candidate[candidateCnt].first = i;
                candidate[candidateCnt++].second = j;
            }
        }
    }
    
    combination(0, 0);
    
    if(Min > 3)
    {
        cout << -1;
    }
    else
    {
        cout << Min;
    }
    
    return 0;
}