15684 Samsung sw test

์ฝ”๋“œ

#include <iostream>
#define MAX_VERTICAL 10
#define MAX_HORIZONTAL 30
#define MAX_LINE 270
 
using namespace std;
 
typedef struct Ladder {
	bool left;
	bool right;
} Ladder;
typedef struct Location {
	int row;
	int col;
} Location;
 
Ladder ladder[MAX_HORIZONTAL][MAX_VERTICAL];
int numOfVertical, numOfHorizontal, numOfLine;
 
int getMinLine();
bool downLadder();
 
int main() {
	cin >> numOfVertical >> numOfLine >> numOfHorizontal;
	for (int i = 0; i < numOfLine; i++) {
		int temp1, temp2;
		cin >> temp1 >> temp2;
 
		ladder[temp1 - 1][temp2 - 1].right = true;
		ladder[temp1 - 1][temp2].left = true;
	}
 
	cout << getMinLine();
}
 
int getMinLine() {
	//0๊ฐœ ์ถ”๊ฐ€
	if (downLadder())
		return 0;
 
	Location location[MAX_HORIZONTAL * MAX_VERTICAL];
	int index = 0;
	for (int height = 0; height < numOfHorizontal; height++) {
		for (int width = 0; width < numOfVertical - 1; width++) {
			if (!ladder[height][width].right && !ladder[height][width].left) {
				location[index].row = height;
				location[index++].col = width;
			}
		}
	}
 
	//1๊ฐœ ์ถ”๊ฐ€
	for (int i = 0; i < index; i++) {
		ladder[location[i].row][location[i].col].right = true;
		ladder[location[i].row][location[i].col + 1].left = true;
		if (downLadder())
			return 1;
		ladder[location[i].row][location[i].col].right = false;
		ladder[location[i].row][location[i].col+1].left = false;
	}
 
	//2๊ฐœ ์ถ”๊ฐ€
	for (int i = 0; i < index-1; i++) {
		ladder[location[i].row][location[i].col].right = true;
		ladder[location[i].row][location[i].col + 1].left = true;
		for (int j = i+1; j < index; j++) {
			if (location[i].row == location[j].row && location[i].col + 1 == location[j].col)
				continue;
			ladder[location[j].row][location[j].col].right = true;
			ladder[location[j].row][location[j].col + 1].left = true;
			if (downLadder())
				return 2;
			ladder[location[j].row][location[j].col].right = false;
			ladder[location[j].row][location[j].col + 1].left = false;
		}
		ladder[location[i].row][location[i].col].right = false;
		ladder[location[i].row][location[i].col+1].left = false;
	}
 
 
	//3๊ฐœ ์ถ”๊ฐ€
	for (int i = 0; i < index - 2; i++) {
		ladder[location[i].row][location[i].col].right = true;
		ladder[location[i].row][location[i].col + 1].left = true;
		for (int j = i + 1; j < index-1; j++) {
			if (location[i].row == location[j].row && location[i].col + 1 == location[j].col)
				continue;
			ladder[location[j].row][location[j].col].right = true;
			ladder[location[j].row][location[j].col + 1].left = true;
			for (int k = j + 1; k < index; k++) {
				if(location[j].row == location[k].row && location[j].col + 1 == location[k].col)
					continue;
				ladder[location[k].row][location[k].col].right = true;
				ladder[location[k].row][location[k].col + 1].left = true;
				if (downLadder())
					return 3;
				ladder[location[k].row][location[k].col].right = false;
				ladder[location[k].row][location[k].col + 1].left = false;
			}
			ladder[location[j].row][location[j].col].right = false;
			ladder[location[j].row][location[j].col + 1].left = false;
		}
		ladder[location[i].row][location[i].col].right = false;
		ladder[location[i].row][location[i].col + 1].left = false;
	}
 
 
	//๊ทธ์™ธ
	return -1;
}
 
bool downLadder() {
	for (int start = 0; start < numOfVertical; start++) {
		int current = start;
		for (int height = 0; height < numOfHorizontal; height++) {
			if (ladder[height][current].left)
				current--;
			else if (ladder[height][current].right)
				current++;
		}
		if (start != current)
			return false;
	}
	return true;
}