20058 Samsung sw test
์ฝ๋
#include <iostream>
#include <list>
#include <cstring>
#define MAX_WIDTH 64
#define MAX_COMMAND 1000
using namespace std;
typedef struct Location {
int row;
int col;
} Location;
int map[MAX_WIDTH][MAX_WIDTH];
int tempMap[MAX_WIDTH][MAX_WIDTH];
int command[MAX_COMMAND];
int width, numOfCommand;
int getRestIce();
int getBigestIce();
void rotate(int row, int col, int length);
int main() {
cin >> width >> numOfCommand;
int temp = 1;
for (int i = 0; i < width; i++)
temp *= 2;
width = temp;
for (int i = 0; i < width; i++)
for (int j = 0; j < width; j++)
cin >> map[i][j];
for (int i = 0; i < numOfCommand; i++)
cin >> command[i];
cout << getRestIce() << endl;
cout << getBigestIce();
}
int getRestIce() {
for (int i = 0; i < numOfCommand; i++) {
int cmd = command[i];
int temp = 1;
for (int i = 0; i < cmd; i++)
temp *= 2;
cmd = temp;
for (int row = 0; row < width; row += cmd)
for (int col = 0; col < width; col += cmd)
rotate(row, col, cmd);
memset(tempMap, 0, sizeof(tempMap));
//์ผ์ ๋
น์ด๊ธฐ
for (int row = 0; row < width; row++) {
for (int col = 0; col < width; col++) {
if (map[row][col] > 0) {
int count = 0;
if (row > 0 && map[row - 1][col] > 0)
count++;
if (col > 0 && map[row][col - 1] > 0)
count++;
if (row < width - 1 && map[row + 1][col] >0)
count++;
if (col < width - 1 && map[row][col + 1] >0)
count++;
if (count < 3)
tempMap[row][col]--;
}
}
}
for (int i = 0; i < width; i++)
for (int j = 0; j < width; j++)
map[i][j] += tempMap[i][j];
}
int count = 0;
for (int i = 0; i < width; i++)
for (int j = 0; j < width; j++)
count += map[i][j];
return count;
}
void rotate(int row, int col, int length) {
for (int i = 0; i < length; i++)
for (int j = 0; j < length; j++)
tempMap[i][j] = map[row + i][col + j];
int tempRow = 0;
for (int i = length - 1; i >= 0; i--) {
for (int j = 0; j < length; j++) {
map[row + j][col + i] = tempMap[tempRow][j];
}
tempRow++;
}
}
int getBigestIce() {
bool visit[MAX_WIDTH][MAX_WIDTH] = { 0, };
int max = 0;
for (int i = 0; i < width; i++) {
for (int j = 0; j < width; j++) {
if (!visit[i][j] && map[i][j] > 0) {
list<Location> q;
q.push_back({ i,j });
int count = -1;
while (!q.empty()) {
Location temp = q.front();
q.pop_front();
count++;
if (temp.row > 0 && !visit[temp.row - 1][temp.col] && map[temp.row - 1][temp.col] > 0) {
q.push_back({ temp.row - 1, temp.col });
visit[temp.row - 1][temp.col] = true;
}
if (temp.col < width - 1 && !visit[temp.row][temp.col + 1] && map[temp.row][temp.col + 1] > 0) {
q.push_back({ temp.row, temp.col + 1 });
visit[temp.row][temp.col + 1] = true;
}
if (temp.row < width - 1 && !visit[temp.row + 1][temp.col] && map[temp.row + 1][temp.col] >0) {
q.push_back({ temp.row + 1, temp.col });
visit[temp.row + 1][temp.col] = true;
}
if (temp.col > 0 && !visit[temp.row][temp.col - 1] && map[temp.row][temp.col - 1] > 0) {
q.push_back({ temp.row, temp.col - 1 });
visit[temp.row][temp.col - 1] = true;
}
}
max = count > max ? count : max;
}
}
}
return max;
}