시뮬레이션과 구현
마법사 상어와 토네이도
4gats
2023. 10. 3. 14:17
https://www.acmicpc.net/problem/20057
20057번: 마법사 상어와 토네이도
마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을
www.acmicpc.net
서 남 동 북 방향으로 로테이션 돌면서
1 1 2 2 3 3 4 4 ...이런 식으로 가는 규칙성이 보인다.
그림을 보면 마지막은 똑같은 숫자가 3번을 돈다!
그게 아니라!
토네이도가 N칸을 움직여야 하는 타이밍이 오게되면, 해당 움직이는 칸 만큼 움직인 후 소멸되어진다
이제 모래를 흩날려보자
방향에 맞게
// 순서대로 동 서 남 북
int xdx[4][10] = { {-1, 1, -1, 1, -1, 1, -2, 2, 0, 0}, {-1, 1, -1, 1, -1, 1, -2, 2, 0, 0},
{0, 0, 1, 1, 2, 2, 1, 1, 3, 2}, {0, 0, -1, -1, -2, -2, -1, -1, -3, -2} };
int ydy[4][10] = { {0, 0, 1, 1, 2, 2, 1, 1, 3, 2}, {0, 0, -1, -1, -2, -2, -1, -1, -3, -2},
{-1, 1, -1, 1, -1, 1, -2, 2, 0, 0}, {-1, 1, -1, 1, -1, 1, -2, 2, 0, 0} };
int percent[9] = { 1, 1, 7, 7 ,10, 10, 2, 2, 5 };
|
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
int n, ans;
int map[505][505];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
// 순서대로 동 서 남 북
int xdx[4][10] = { {-1, 1, -1, 1, -1, 1, -2, 2, 0, 0}, {-1, 1, -1, 1, -1, 1, -2, 2, 0, 0},
{0, 0, 1, 1, 2, 2, 1, 1, 3, 2}, {0, 0, -1, -1, -2, -2, -1, -1, -3, -2} };
int ydy[4][10] = { {0, 0, 1, 1, 2, 2, 1, 1, 3, 2}, {0, 0, -1, -1, -2, -2, -1, -1, -3, -2},
{-1, 1, -1, 1, -1, 1, -2, 2, 0, 0}, {-1, 1, -1, 1, -1, 1, -2, 2, 0, 0} };
int percent[9] = { 1, 1, 7, 7 ,10, 10, 2, 2, 5 };
int change_dir(int dir)
{
if (dir == 0) return 3;
if (dir == 1) return 2;
if (dir == 2) return 0;
if (dir == 3) return 1;
}
void spread(int x, int y, int dir)
{
int xx = x + dx[dir];
int yy = y + dy[dir];
if (map[xx][yy] == 0)
return;
int sand = map[xx][yy];
int tmp = sand;
for (int i = 0; i < 9; i++)
{
int nx = x + xdx[dir][i];
int ny = y + ydy[dir][i];
int per = percent[i];
int plus = (tmp * per) / 100;
if (nx < 1 || ny < 1 || nx > n || ny > n)
ans += plus;
else
map[nx][ny] += plus;
sand -= plus;
}
int nx = x + xdx[dir][9];
int ny = y + ydy[dir][9];
if (nx == 0 || ny == 0 || nx > n || ny > n)
ans += sand;
else
map[nx][ny] += sand;
map[xx][yy] = 0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> map[i][j];
}
}
int x = (n + 1) / 2;
int y = (n + 1) / 2;
int dir = 1; // 서쪽으로 start
int move_cnt = 1;
while (true)
{
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < move_cnt; j++)
{
spread(x, y, dir);
x += dx[dir];
y += dy[dir];
}
dir = change_dir(dir);
}
move_cnt++;
// 마지막은 한번만 가면 됨
if (move_cnt == n)
{
for (int j = 0; j < move_cnt - 1; j++)
{
spread(x, y, dir);
x += dx[dir];
y += dy[dir];
}
break;
}
}
cout << ans << '\n';
return 0;
}
|
cs |