문제 요약
마법사 상어가 토네이도를 일으키며 먼지를 뿌리고 다니는 걸 시뮬레이션 하라!
환경
- N*N격자의 (N<499, N은 홀수)중심서부터 토네이도가 한 칸씩 돕니다.
- 토네이도의 중심에는 모래가 없습니다.
- 격자 바깥으로 나가는 모래의 양을 구하세요!
- 모래가 움직였을 때, 도착한 칸에 모래가 있다면 모래의 양이 합쳐집니다.
초기 상태
- 토네이도는 중심에서 왼쪽으로 가는 방향으로 시작됩니다.
1회 당 규칙
- 토네이도 중심이 x에서 y로 움직일 때 위 사진과 같이 y에 있는 모래들이 퍼진다.
- 퍼지고 남은 모래는 @로 밀려나고,
y에는 모래가 없이 비게 된다.
아이디어
정확한 시뮬레이션
주의할점1. x와 y의 매핑
단계 시작 -> ⓧ -> 중심 움직임 -> ⓨ -> 모래 흩날림 -> ⓐ를 x에서 y 구하듯이 구함 -> y에 모래를 비우고 a에 남은 모래를 넣음
으로 구현했다.
문제에 써있는대로 아주 정확하게 중심이 움직이자마자 y에 모래를 비우는 것도 좋았을 것 같다.
주의할점2. 남은 모래를 구하기
주변으로 ~~%가 흩어지는 것이다! ~~%만큼 빠진데서 복리처럼 ~~%를 또 계산하는 게 아니다!
팁
2차원 배열의 값 배정
소스
#include<iostream>
#include<iomanip>
using namespace std;
int arr[500][500];//499도 됨
int N;
int sum_out = 0;
int knl[4][5][5];
bool in_box(int i, int j) {
return i >= 0 && i < N&& j >= 0 && j < N;
}
int new_d(int d) {
if(d == 3){
d = 0;
}
else {
d++;
}
return d;
}
int power(int mi, int mj,int v) {
int si = mi - 2, sj = mj - 2;
int mother = arr[mi][mj];
int left = mother;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
int child = mother * ((double)knl[v][i][j] / (double)100);
if (child == 0) continue;
left -= child;
if (in_box(si + i, sj + j)) {
arr[si + i][sj + j] += child;
}
else {
sum_out += child;
}
}
}
return left;
}
int di[] = { 0, 1,0,-1 };
int dj[] = { -1,0,1,0 };
int **ker;
int r0[] = { 0,0,2,0,0 };
int r1[] = { 0,10,7,1,0 };
int r2[] = { 5, 0, 0,0,0 };
int main() {
ker = new int* [5];
ker[0] = r0; ker[1] = r1; ker[2] = r2; ker[3] = r1; ker[4] = r0;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
knl[0][i][j] = ker[i][j];
knl[1][4 - j][i] = ker[i][j];
knl[2][4 - i][4 - j] = ker[i][j];
knl[3][j][4 - i] = ker[i][j];
}
}
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> arr[i][j];
}
}
int mid = N / 2;
int sz = 1;
int lsz = sz;//left size
int i = mid, j = mid;
int d = 0;
int ctr = 0;
while (true) {
i += di[d]; j += dj[d];//y
lsz--;
int a = power(i, j, d);
int ai = i + di[d], aj = j + dj[d];
if (in_box(ai, aj)) {
arr[ai][aj] += a;
arr[i][j] = 0;
}
else {
sum_out += a;
}
if (i == 0 && j == 0) {
break;
}
if (lsz == 0) {
if (d == 1||d ==3) {
sz++;
}
lsz = sz;
d = new_d(d);
}
ctr++;
}
cout << sum_out << endl;
}