14502 Samsung sw test
์ฝ๋
#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;
}