15684 사다리 조작

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

15684번: 사다리 조작

유형: 시뮬레이션

• 재귀를 이용하여 막대기의 조합 만들기. (선택,비선택)
• check함수를 만들어 col이 원 위치로 오는지 확인

/*
	1. 막대기를 먼저 다 놓는다.
	2. 제자리로 오는지 확인한다.
	main
		입력
	sol
		if index==4 || pos가 끝자리인 경우
			if check
				
			끝
		r,c 구하기
		if map[r][c] ==0 && map[r][c+1]==0 
			막대기 놓기 가능
			map[r][c]=left
			map[r][c+1]=right
			sol (index+1, pos+1)
			다시 0으로 초기화
		sol(index,pos+1)

	check
		for c
			for r
				map이 right면 c을 하나 증가
				map이 left면 c을 하나 빼기
			if pos하고 c하고 틀리면 return

				
*/
#include<iostream>
#include<algorithm>
using namespace std;
int LEFT = 1;
int RIGHT = 2;
int N, M, H;
int map[30][10] = { 0, };
int ans=300;
bool check() {
	for (int c = 0; c < N; c++) 
	{
		int pos = c;
		for (int r = 0; r < H ; r++) {
			if (map[r][pos] == RIGHT) {
				pos++;
			}
			else if (map[r][pos] == LEFT) {
				pos--;
			}
		}
		if (pos != c) return false;
	}
	return true;
}
void sol(int index,int pos) {
	if (index == 3 || pos > H * N) {
		if (check()) {
			ans = min(ans, index);
		}
		return;
	}
	int row = pos / N;
	int col = pos % N;
	if (col+1<N && map[row][col] == 0 && map[row][col+1] == 0) {
		map[row][col] = RIGHT;
		map[row][col + 1] = LEFT;
		sol(index + 1, pos+2);
		map[row][col] = 0;
		map[row][col + 1] = 0;
	}
	sol(index, pos + 1);
}
int main() {
	cin >> N >> M >> H;
	for (int i = 0; i < M; i++) {
		int y, x;
		cin >> y >> x;
		--y; --x;
		map[y][x] = RIGHT;
		map[y][x + 1] = LEFT;
	}
	
	sol(0,0);
	if (ans == 300)
	{
		cout << -1;
	}
	else
	{
		cout << ans;
	}
}