사다리조작_15684

문제 출처 : 사다리조작

파라미터 정리

N 세로선(col), M 가로선(연결선), H 점선(row)
사다리 게임이 진행되는 방법 : 아래(r+1), 좌측(c-1),우측(c+1) 中 택1
가로선은 연속하거나 서로 접하면 안됨
원하는 것 = 가로선을 추가하여 모든 i번 세로줄의 결과가 i번으로 나와야 함
이때 추가해야 하는 가로선 개수의 최솟값을 반환하기

간략한 과정

input_1 N,M,H 입력받기 (2~N~10) (1~H~30) (0~M~(N-1)xH)
input_2 처음 가로선(M)의 정보를 입력받기
(a,b)로 입력받으며 a점선 위치에서 b세로, b+1 세로가 연결된 것을 의미함 (1~a~H, 1~b~N-1)
해당 지점에 Left/Right 표시해두기
res = INF
원래 맵 정보 저장해두기
가로선을 n개 추가하는 경우 만들기{
n은 0부터 시작해서 점점 증가함, n >3이면 break 후 -1 반환
가로선이 접하는 지 확인하고 조건이 충족되는 곳에 가로선 추가하기xn번
해당 지점에 Left/Right 표시해두기
i번째 세로줄의 결과가 모두 i로 나오는지 확인
T -> res = n
F -> 원래 맵 정보 다시 가져온 후, 다른 위치에 사다리 그리기 -> n증가
}
ouput res 반환하기

코드

#include <iostream>

using namespace std;

#define INF 984565754
#define RIGHT 1
#define LEFT 2

int N,M,H;//H row//N col
int Map[30][10] = {0};

bool check(){
    
    for(int i = 0; i < N; i++){
        int row = 0,col = i;
        do{
            if(Map[row][col] == LEFT)
                col--;
            else if(Map[row][col] == RIGHT)
                col++;
            row++;
        }while(row!=H);
        if(i != col) return false;
    }
    
    return true;
}

int solve(int pos, int cnt){
    if(cnt == 3 || pos >= (H*N)){
        if(check()) return cnt;
        return INF;
    }
    int res = INF;
    int row = pos/N, col = pos%N;
    if(col < N-1 && Map[row][col] == 0 && Map[row][col+1] == 0){
        Map[row][col] = RIGHT;
        Map[row][col+1] = LEFT;
        res = min(res, solve(pos+2, cnt+1));
        Map[row][col] = 0;
        Map[row][col+1] = 0;
    }
    
    res = min(res,solve(pos+1,cnt));
   
    return res;
}

int main()
{
    cin >> N >> M >> H;
    
    
    for(int i = 0; i < M; i++){
        //초기 가로선 입력받기
        int a,b;
        cin >> a >> b;
        Map[a-1][b-1] = RIGHT;
        Map[a-1][b] = LEFT;
    }
    
    int res = solve(0,0);
    if(res == INF)  res = -1;
    cout << res << endl;
    
    return 0;
}