[ λ°±μ€ / BOJ 20057 ] λ§λ²μ¬ μμ΄μ ν λ€μ΄λ ( μλ° / JAVA )
https://www.acmicpc.net/problem/20057
20057λ²: λ§λ²μ¬ μμ΄μ ν λ€μ΄λ
λ§λ²μ¬ μμ΄κ° ν λ€μ΄λλ₯Ό λ°°μ κ³ , μ€λμ ν λ€μ΄λλ₯Ό ν¬κΈ°κ° N×NμΈ κ²©μλ‘ λλμ΄μ§ λͺ¨λλ°μμ μ°μ΅νλ €κ³ νλ€. μμΉ (r, c)λ 격μμ rν cμ΄μ μλ―Ένκ³ , A[r][c]λ (r, c)μ μλ λͺ¨λμ μμ
www.acmicpc.net
λ¬Έμ μ€λͺ
ν λ€μ΄λ μμ μ
λ°©μμΌλ‘ μ΄λμ΄ μμλ¨
xκ° yλ‘ μ΄λν λ, yμ λͺ¨λκ° λΉμ¨κ³Ό $\alpha$κ° μ νμλ μΉΈμΌλ‘ μ΄λ
$\alpha$ = μ΄ μ - λΉμ¨ μΉΈ μ΄λμ
λͺ¨λλ λ²μ λ°μΌλ‘ μ΄λ κ°λ₯! π μ¬λΌμ§
ν λ€μ΄λλ (0,0)κΉμ§ μ΄λν λ€ μλ©Έλ¨
μλ©Έλ ν, 격μ λ°μΌλ‘ λκ° λͺ¨λμ μ μΆλ ₯
λ¬Έμ νμ΄
λ°©ν₯μ λ°λΌ λΏλ €μ§λ μμΉ
μ΄λλ°©ν₯ | ← | ↓ | → | ↑ |
---|---|---|---|---|
μ΄λνμ | 1,3,5,..., | 1,3,5,..., | 2,4,6,..., | 2,4,6,..., |
λͺ¨λ νμ° λ°©ν₯ | ![]() |
![]() |
![]() |
![]() |
dx/dyOfSand[4][9]
π 4λ°©ν₯μμ κ° λΉμ¨μ μμΉratioOfSand[9]
π dx/dyOfSand μμλλ‘μ λΉμ¨ {2, 10, 7, 1, 5, 10, 7, 1, 2}
νμ νλ©΄μ, λͺ¨λκ° νΌμ§λ μμΉ(x,y)κ° (x < 0 || y < 0 || N <= x || N <= y)μ΄λ©΄amountOfOutSand
μ μΆκ°ν΄μ€λ€
~
!!!
μ½λ
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_BOJ_20057_λ§λ²μ¬_μμ΄μ_ν λ€μ΄λ {
static int N, amountOfOutSand = 0;
static int[][] map;
static int[] dx = {0, 1, 0, -1};
static int[] dy = {-1, 0, 1, 0};
static int[] numOfMove = {1, 1, 2, 2};
static int[][] dxOfSand = {{-2, -1, -1, -1, 0, 1, 1, 1, 2}, {0, 1, 0, -1, 2, 1, 0, - 1, 0}, {2, 1, 1, 1, 0, -1, -1, -1, -2}, {0, -1, 0, 1, -2, -1, 0, 1, 0}};
static int[][] dyOfSand = {{0, -1, 0, 1, -2, -1, 0, 1, 0}, {-2, -1, -1, -1, 0, 1, 1, 1, 2}, {0, 1, 0, -1, 2, 1, 0, -1, 0}, {2, 1, 1, 1, 0, -1, -1, -1, -2}};
static int[] ratioOfSand = {2, 10, 7, 1, 5, 10, 7, 1, 2};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stringTokenizer;
N = Integer.parseInt(br.readLine());
map = new int[N][N];
for (int i = 0; i < N; i++) {
stringTokenizer = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(stringTokenizer.nextToken());
}
}
tornado(N / 2, N / 2);
System.out.println(amountOfOutSand);
}
private static void tornado(int x, int y) {
int curX = x;
int curY = y;
while (true) {
for (int d = 0; d < 4; d++) {
for (int i = 0; i < numOfMove[d]; i++) {
int nx = curX + dx[d];
int ny = curY + dy[d];
if (nx < 0 || ny < 0 || N <= nx || N <= ny) return;
int sand = map[nx][ny];
map[nx][ny] = 0;
int spreadTotal = 0;
for (int s = 0; s < 9; s++) {
int sandX = nx + dxOfSand[d][s];
int sandY = ny + dyOfSand[d][s];
int spreadAmount = (sand * ratioOfSand[s]) / 100;
if (sandX < 0 || sandY < 0 || N <= sandX || N <= sandY) amountOfOutSand += spreadAmount;
else map[sandX][sandY] += spreadAmount;
spreadTotal += spreadAmount;
}
int alphaX = nx + dx[d];
int alphaY = ny + dy[d];
int amountOfAlpha = sand - spreadTotal;
if (alphaX < 0 || alphaY < 0 || N <= alphaX || N <= alphaY) amountOfOutSand += amountOfAlpha;
else map[alphaX][alphaY] += amountOfAlpha;
curX = nx;
curY = ny;
/*for(int[] ma : map){
for(int m : ma){
System.out.print(m+" ");
}
System.out.println();
}
System.out.println();*/
}
}
for (int i = 0; i < 4; i++) {
numOfMove[i] += 2;
}
}
}
}