14502 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
#include <iostream>
#include <list>
#include <cstring>
#define MAX_WIDTH 8
using namespace std;
typedef struct Cell {
int row;
int col;
} Cell;
int map[MAX_WIDTH][MAX_WIDTH];
int tempMap[MAX_WIDTH][MAX_WIDTH];
int width, height;
int getMaxSafeArea();
int main() {
cin >> height >> width;
for (int i = 0; i < height; i++)
for (int j = 0; j < width; j++)
cin >> map[i][j];
cout << getMaxSafeArea();
}
int getMaxSafeArea() {
int maxSafeArea = 0;
int last = height * width - 2;
int last2 = height * width - 1;
int last3 = height * width;
for (int start = 0; start < last; start++) {
int startRow = start / width;
int startCol = start % width;
if (map[startRow][startCol] != 0)
continue;
for (int start2 = start + 1; start2 < last2; start2++) {
int start2Row = start2 / width;
int start2Col = start2 % width;
if (map[start2Row][start2Col] != 0)
continue;
for (int start3 = start2 + 1; start3 < last3; start3++) {
int start3Row = start3 / width;
int start3Col = start3 % width;
if (map[start3Row][start3Col] != 0)
continue;
for (int i = 0; i < MAX_WIDTH; i++)
memcpy(tempMap[i], map[i], sizeof(int) * MAX_WIDTH);
tempMap[startRow][startCol] = 1;
tempMap[start2Row][start2Col] = 1;
tempMap[start3Row][start3Col] = 1;
list<Cell> queue;
for (int i = 0; i < height; i++)
for (int j = 0; j < width; j++)
if (tempMap[i][j] == 2)
queue.push_back({ i, j });
while (!queue.empty()) {
Cell current = queue.front();
queue.pop_front();
if (current.row - 1 >= 0 && tempMap[current.row - 1][current.col] == 0) {
tempMap[current.row - 1][current.col] = 2;
queue.push_back({ current.row - 1, current.col });
}
if (current.row + 1 < height && tempMap[current.row + 1][current.col] == 0) {
tempMap[current.row + 1][current.col] = 2;
queue.push_back({ current.row + 1, current.col });
}
if (current.col - 1 >= 0 && tempMap[current.row][current.col - 1] == 0) {
tempMap[current.row][current.col - 1] = 2;
queue.push_back({ current.row, current.col - 1 });
}
if (current.col + 1 < width && tempMap[current.row][current.col + 1] == 0) {
tempMap[current.row][current.col + 1] = 2;
queue.push_back({ current.row, current.col + 1 });
}
}
int temp = 0;
for (int i = 0; i < height; i++)
for (int j = 0; j < width; j++)
if (tempMap[i][j] == 0)
temp++;
maxSafeArea = temp > maxSafeArea ? temp : maxSafeArea;
}
}
}
return maxSafeArea;
}