15684 Samsung sw test
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#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;
}