- 마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다.
struct cloud { void location_clearance(const int basket_size) { y = (y >= basket_size ? y % basket_size : y < 0 ? (basket_size * 30 + y) % basket_size : y); x = (x >= basket_size ? x % basket_size : x < 0 ? (basket_size * 30 + x) % basket_size : x); } int y; int x; };
- 비바라기를 시전하면 (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 비구름이 생긴다
void clouds_initialize(vector<cloud>& clouds, const int basket_size) { clouds.push_back({ basket_size - 1, 0 }); clouds.push_back({ basket_size - 1, 1 }); clouds.push_back({ basket_size - 2, 0 }); clouds.push_back({ basket_size - 2, 1 }); }
- 이동 명령 방향은 총 8개의 방향이 있으며, 8개의 정수로 표현한다. 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다.
// global variable // 1부터 이기에 moving[0]에 아무값이나 대입 constexpr int moving[9][2] = { {0,0}, {0,-1}, {-1,-1},{-1,0},{-1,1},{0,1},{1, 1},{1,0},{1,-1} }; // ----
- 모든 구름이 di 방향으로 si칸 이동한다.
void move_clouds(vector<vector<int>>& baskets, vector<cloud>& clouds, vector<vector<bool>>& clouds_location, const int basket_size, const int move_direction, const int move_squares) { for (cloud& cloud : clouds) { cloud.y += (moving[move_direction][0]) * move_squares; cloud.x += (moving[move_direction][1]) * move_squares; // 격자의 연결 cloud.location_clearance(basket_size); // 2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다. baskets[cloud.y][cloud.x]++; // 구름들의 위치를 담는 배열 5번 조건에서 사용 clouds_location[cloud.y][cloud.x] = true; } }
- 구름이 모두 사라진다.
vector<cloud>().swap(clouds); // free
- 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.
void water_copy_burg(vector<vector<int>>& baskets, const vector<cloud>& clouds, const int basket_size) { // 선행으로 복사되어서 증가한 칸이 다음에 진행할 칸에 영향을 미치지 않게 하기 위한 임시 배열 vector<vector<int>> copy_baskets(baskets); for (const cloud cloud : clouds) { for (int i = 2; i <= 8; i += 2) // ↖, ↗, ↘, ↙ 방향 탐색 { const int y = cloud.y + moving[i][0]; const int x = cloud.x + moving[i][1]; if (check_area(basket_size, y, x) || baskets[y][x] == 0) { continue; } copy_baskets[cloud.y][cloud.x]++; } } baskets.swap(copy_baskets); } // ----- // 4-1. 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다. bool check_area(const int basket_size, const int y, const int x) { return y < 0 || y >= basket_size || x < 0 || x >= basket_size; }
- 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.
void make_clouds(vector<vector<int>>& baskets, vector<cloud>& clouds, vector<vector<bool>>& clouds_location, const int basket_size) { for (int i = 0; i < basket_size; i++) { for (int j = 0; j < basket_size; j++) { // 3에서 구름이 사라진 칸이 아니어야 한다. if (clouds_location[i][j]) { clouds_location[i][j] = false; continue; } // 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. if (baskets[i][j] > 1) { clouds.push_back({ i, j }); baskets[i][j] -= 2; clouds_location[i][j] = true; } } } }
- 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 구해보자.
int print_water_sum(const vector<vector<int>>& baskets, const int basket_size) { int sum = 0; for (int i = 0; i < basket_size; i++) { for (int j = 0; j < basket_size; j++) { sum += baskets[i][j]; } } return sum; }
각각 구현한 조건들을 순서에 맞게 조합한다!
#include<bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
constexpr int moving[9][2] = { {0,0}, {0,-1}, {-1,-1},{-1,0},{-1,1},{0,1},{1, 1},{1,0},{1,-1} };
struct cloud
{
void location_clearance(const int basket_size)
{
y = (y >= basket_size ? y % basket_size : y < 0 ? (basket_size * 30 + y) % basket_size : y);
x = (x >= basket_size ? x % basket_size : x < 0 ? (basket_size * 30 + x) % basket_size : x);
}
int y;
int x;
};
void clouds_initialize(vector<cloud>& clouds, const int basket_size)
{
clouds.push_back({ basket_size - 1, 0 });
clouds.push_back({ basket_size - 1, 1 });
clouds.push_back({ basket_size - 2, 0 });
clouds.push_back({ basket_size - 2, 1 });
}
bool check_area(const int basket_size, const int y, const int x)
{
return y < 0 || y >= basket_size || x < 0 || x >= basket_size;
}
void make_clouds(vector<vector<int>>& baskets, vector<cloud>& clouds, vector<vector<bool>>& clouds_location, const int basket_size)
{
for (int i = 0; i < basket_size; i++)
{
for (int j = 0; j < basket_size; j++)
{
if (clouds_location[i][j])
{
clouds_location[i][j] = false;
continue;
}
if (baskets[i][j] > 1)
{
clouds.push_back({ i, j });
baskets[i][j] -= 2;
clouds_location[i][j] = true;
}
}
}
}
void water_copy_burg(vector<vector<int>>& baskets, const vector<cloud>& clouds, const int basket_size)
{
vector<vector<int>> copy_baskets(baskets);
for (const cloud cloud : clouds)
{
for (int i = 2; i <= 8; i += 2)
{
const int y = cloud.y + moving[i][0];
const int x = cloud.x + moving[i][1];
if (check_area(basket_size, y, x) || baskets[y][x] == 0)
{
continue;
}
copy_baskets[cloud.y][cloud.x]++;
}
}
baskets.swap(copy_baskets);
}
void move_clouds(vector<vector<int>>& baskets, vector<cloud>& clouds, vector<vector<bool>>& clouds_location, const int basket_size, const int move_direction, const int move_squares)
{
for (cloud& cloud : clouds)
{
cloud.y += (moving[move_direction][0]) * move_squares;
cloud.x += (moving[move_direction][1]) * move_squares;
cloud.location_clearance(basket_size);
baskets[cloud.y][cloud.x]++;
clouds_location[cloud.y][cloud.x] = true;
}
}
void wising_rain(vector<vector<int>>& baskets, const int basket_size, int move_command_size)
{
vector<cloud> clouds;
clouds_initialize(clouds, basket_size);
while (move_command_size--)
{
vector<vector<bool>> clouds_location(basket_size, vector<bool>(basket_size));
int move_direction, move_squares;
cin >> move_direction >> move_squares;
move_clouds(baskets, clouds, clouds_location, basket_size, move_direction, move_squares);
water_copy_burg(baskets, clouds, basket_size);
vector<cloud>().swap(clouds); // free
make_clouds(baskets, clouds, clouds_location, basket_size);
}
}
int print_water_sum(const vector<vector<int>>& baskets, const int basket_size)
{
int sum = 0;
for (int i = 0; i < basket_size; i++)
{
for (int j = 0; j < basket_size; j++)
{
sum += baskets[i][j];
}
}
return sum;
}
int main() {
FAST_IO;
int basket_size, move_command_size;
cin >> basket_size >> move_command_size;
vector<vector<int>> baskets(basket_size, vector<int>(basket_size));
for (int i = 0; i < basket_size; i++)
{
for (int j = 0; j < basket_size; j++)
{
cin >> baskets[i][j];
}
}
wising_rain(baskets, basket_size, move_command_size);
cout << print_water_sum(baskets, basket_size) << '\n';
return 0;
}