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;
}