๋ฏธ์ธ๋จผ์ง๋ฅผ ์ ๊ฑฐํ๊ธฐ ์ํด ๊ตฌ์ฌ๊ณผ๋ ๊ณต๊ธฐ์ฒญ์ ๊ธฐ๋ฅผ ์ค์นํ๋ ค๊ณ ํ๋ค. ๊ณต๊ธฐ์ฒญ์ ๊ธฐ์ ์ฑ๋ฅ์ ํ ์คํธํ๊ธฐ ์ํด ๊ตฌ์ฌ๊ณผ๋ ์ง์ ํฌ๊ธฐ๊ฐ RรC์ธ ๊ฒฉ์ํ์ผ๋ก ๋ํ๋๊ณ , 1ร1 ํฌ๊ธฐ์ ์นธ์ผ๋ก ๋๋ด๋ค. ๊ตฌ์ฌ๊ณผ๋ ๋ฐ์ด๋ ์ฝ๋ฉ ์ค๋ ฅ์ ์ด์ฉํด ๊ฐ ์นธ (r, c)์ ์๋ ๋ฏธ์ธ๋จผ์ง์ ์์ ์ค์๊ฐ์ผ๋ก ๋ชจ๋ํฐ๋งํ๋ ์์คํ ์ ๊ฐ๋ฐํ๋ค. (r, c)๋ rํ c์ด์ ์๋ฏธํ๋ค.
๊ณต๊ธฐ์ฒญ์ ๊ธฐ๋ ํญ์ 1๋ฒ ์ด์ ์ค์น๋์ด ์๊ณ , ํฌ๊ธฐ๋ ๋ ํ์ ์ฐจ์งํ๋ค. ๊ณต๊ธฐ์ฒญ์ ๊ธฐ๊ฐ ์ค์น๋์ด ์์ง ์์ ์นธ์๋ ๋ฏธ์ธ๋จผ์ง๊ฐ ์๊ณ , (r, c)์ ์๋ ๋ฏธ์ธ๋จผ์ง์ ์์ Ar,c์ด๋ค.
1์ด ๋์ ์๋ ์ ํ ์ผ์ด ์์๋๋ก ์ผ์ด๋๋ค.
1. ๋ฏธ์ธ๋จผ์ง๊ฐ ํ์ฐ๋๋ค. ํ์ฐ์ ๋ฏธ์ธ๋จผ์ง๊ฐ ์๋ ๋ชจ๋ ์นธ์์ ๋์์ ์ผ์ด๋๋ค.
- (r, c)์ ์๋ ๋ฏธ์ธ๋จผ์ง๋ ์ธ์ ํ ๋ค ๋ฐฉํฅ์ผ๋ก ํ์ฐ๋๋ค.
์ธ์ ํ ๋ฐฉํฅ์ ๊ณต๊ธฐ์ฒญ์ ๊ธฐ๊ฐ ์๊ฑฐ๋, ์นธ์ด ์์ผ๋ฉด ๊ทธ ๋ฐฉํฅ์ผ๋ก๋ ํ์ฐ์ด ์ผ์ด๋์ง ์๋๋ค.- ํ์ฐ๋๋ ์์ Ar,c/5์ด๊ณ ์์์ ์ ๋ฒ๋ฆฐ๋ค.
- (r, c)์ ๋จ์ ๋ฏธ์ธ๋จผ์ง์ ์์ Ar,c - (Ar,c/5)ร(ํ์ฐ๋ ๋ฐฉํฅ์ ๊ฐ์) ์ด๋ค.
- ๊ณต๊ธฐ์ฒญ์ ๊ธฐ๊ฐ ์๋ํ๋ค.
- ๊ณต๊ธฐ์ฒญ์ ๊ธฐ์์๋ ๋ฐ๋์ด ๋์จ๋ค.
- ์์ชฝ ๊ณต๊ธฐ์ฒญ์ ๊ธฐ์ ๋ฐ๋์ ๋ฐ์๊ณ๋ฐฉํฅ์ผ๋ก ์ํํ๊ณ , ์๋์ชฝ ๊ณต๊ธฐ์ฒญ์ ๊ธฐ์ ๋ฐ๋์ ์๊ณ๋ฐฉํฅ์ผ๋ก ์ํํ๋ค.
- ๋ฐ๋์ด ๋ถ๋ฉด ๋ฏธ์ธ๋จผ์ง๊ฐ ๋ฐ๋์ ๋ฐฉํฅ๋๋ก ๋ชจ๋ ํ ์นธ์ฉ ์ด๋ํ๋ค.
- ๊ณต๊ธฐ์ฒญ์ ๊ธฐ์์ ๋ถ๋ ๋ฐ๋์ ๋ฏธ์ธ๋จผ์ง๊ฐ ์๋ ๋ฐ๋์ด๊ณ , ๊ณต๊ธฐ์ฒญ์ ๊ธฐ๋ก ๋ค์ด๊ฐ ๋ฏธ์ธ๋จผ์ง๋ ๋ชจ๋ ์ ํ๋๋ค.
๋ค์์ ํ์ฐ์ ์์์ด๋ค.
์ผ์ชฝ๊ณผ ์ค๋ฅธ์ชฝ์ ์นธ์ด ์๊ธฐ ๋๋ฌธ์, ๋ ๋ฐฉํฅ์ผ๋ก๋ง ํ์ฐ์ด ์ผ์ด๋ฌ๋ค.
์ธ์ ํ ๋ค ๋ฐฉํฅ์ผ๋ก ๋ชจ๋ ํ์ฐ์ด ์ผ์ด๋๋ค.
๊ณต๊ธฐ์ฒญ์ ๊ธฐ๊ฐ ์๋ ์นธ์ผ๋ก๋ ํ์ฐ์ด ์ผ์ด๋์ง ์๋๋ค.
๊ณต๊ธฐ์ฒญ์ ๊ธฐ์ ๋ฐ๋์ ๋ค์๊ณผ ๊ฐ์ ๋ฐฉํฅ์ผ๋ก ์ํํ๋ค.
๋ฐฉ์ ์ ๋ณด๊ฐ ์ฃผ์ด์ก์ ๋, T์ด๊ฐ ์ง๋ ํ ๊ตฌ์ฌ๊ณผ์ ๋ฐฉ์ ๋จ์์๋ ๋ฏธ์ธ๋จผ์ง์ ์์ ๊ตฌํด๋ณด์.
์ ๋ ฅ
์ฒซ์งธ ์ค์ R, C, T (6 โค R, C โค 50, 1 โค T โค 1,000) ๊ฐ ์ฃผ์ด์ง๋ค.
๋์งธ ์ค๋ถํฐ R๊ฐ์ ์ค์ Ar,c (-1 โค Ar,c โค 1,000)๊ฐ ์ฃผ์ด์ง๋ค. ๊ณต๊ธฐ์ฒญ์ ๊ธฐ๊ฐ ์ค์น๋ ๊ณณ์ Ar,c๊ฐ -1์ด๊ณ , ๋๋จธ์ง ๊ฐ์ ๋ฏธ์ธ๋จผ์ง์ ์์ด๋ค. -1์ 2๋ฒ ์์๋๋ก ๋ถ์ด์ ธ ์๊ณ , ๊ฐ์ฅ ์ ํ, ์๋ซ ํ๊ณผ ๋ ์นธ์ด์ ๋จ์ด์ ธ ์๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ T์ด๊ฐ ์ง๋ ํ ๊ตฌ์ฌ๊ณผ ๋ฐฉ์ ๋จ์์๋ ๋ฏธ์ธ๋จผ์ง์ ์์ ์ถ๋ ฅํ๋ค.
๐ก ๊ณต๊ธฐ์ฒญ์ ๊ธฐ์ ์์น๋ฅผ ๊ตฌํจ
๐ก ๋ฏธ์ธ๋จผ์ง ์ฐพ๊ธฐ
๋ฏธ์ธ๋จผ์ง๊ฐ ์๋ ๊ณณ์ ์์น์ ๋ฏธ์ธ๋จผ์ง๋ฅผ Node์ ์ ์ฅํ๊ณ ์ด๋ฅผ ํ์ ๋ฃ์
๐ก ํ์ฐ
ํ์ ๋ฃ์ ์์น๋ฅผ ๊บผ๋ด์ 5๋ก ๋๋์ด์ฃผ๊ณ ์ฌ๋ฐฉ์ผ๋ก ํ์ฐ์ํด
ํ์ฐ์ํจ ์๋งํผ ๋นผ์ค
๐ก ๊ณต๊ธฐ์ฒญ์
๊ณต๊ธฐ์ฒญ์ ๊ธฐ์ ์์น๋ฅผ ๊ตฌํด ์ ์๋๋ก ๋๋ ๋ค์,
์์๋ ์๊ณ๋ฐฉํฅ, ์๋๋ ๋ฐ์๊ณ๋ฐฉํฅ์ผ๋ก ๋ฐฐ์ด์ ์์ง์
๊ณต๊ธฐ์ฒญ์ ๊ธฐ์์ ๋ฐ๋ก ๋์ค๋ ๊ณต๊ธฐ๋ ๋ฏธ์ธ๋จผ์ง๊ฐ ์์!!
๐ก ๋ฏธ์ธ๋จผ์ง ์ฐพ๊ธฐ ~ ๊ณต๊ธฐ์ฒญ์ ๊น์ง๋ฅผ T๋งํผ ๋ฐ๋ณตํจ
๐ก ๋ฐฐ์ด์ ์๋ ๋ฏธ์ธ๋จผ์ง๋ฅผ ๋ชจ๋ ๋ํจ
if(map[i][j] == -1 && cleaner == -1) {
cleaner = i;
}
q = new LinkedList<>();
for(int i=0; i<R; i++) {
for(int j=0; j<C; j++) {
if(map[i][j] != 0 && map[i][j] != -1) {
q.add(new Node(i,j,map[i][j]));
}
}
}
static void diffusion() {
while(!q.isEmpty()) {
Node cur = q.poll();
int dust = cur.d/5;
int count = 0;
if(dust == 0)
continue;
for(int i=0; i<4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if(nx < 0 || nx >= R || ny<0 || ny>=C || map[nx][ny] == -1)
continue;
count++;
map[nx][ny] += dust;
}
map[cur.x][cur.y] -= dust*count;
}
}
static void wind(int cleaner) {
int up = cleaner;
int down = cleaner+1;
for(int i=up-1; i>0; i--) {
map[i][0] = map[i-1][0];
}
for(int i=0; i<C-1; i++) {
map[0][i] = map[0][i+1];
}
for(int i=0; i<up; i++) {
map[i][C-1] = map[i+1][C-1];
}
for(int i=C-1; i>1; i--) {
map[up][i] = map[up][i-1];
}
map[up][1] = 0;
for(int i=down+1; i<R-1; i++) {
map[i][0] = map[i+1][0];
}
for(int i=0; i<C-1; i++) {
map[R-1][i] = map[R-1][i+1];
}
for(int i=R-1; i>down; i--) {
map[i][C-1] = map[i-1][C-1];
}
for(int i=C-1; i>1; i--) {
map[down][i] = map[down][i-1];
}
map[down][1] = 0;
}
while(T-->0) {
q = new LinkedList<>();
for(int i=0; i<R; i++) {
for(int j=0; j<C; j++) {
if(map[i][j] != 0 && map[i][j] != -1) {
q.add(new Node(i,j,map[i][j]));
}
}
}
diffusion();
wind(cleaner);
}
static int cal() {
int sum = 0;
for(int i=0; i<R; i++) {
for(int j=0; j<C; j++) {
if(map[i][j] != -1 && map[i][j] != 0)
sum += map[i][j];
}
}
return sum;
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.LinkedList;
public class Imple_13 {
static int[][] map;
static Queue<Node> q;
static int[] dx = {0,0,-1,1};
static int[] dy = {1,-1,0,0};
static int R, C, T;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
R = Integer.parseInt(s[0]);
C = Integer.parseInt(s[1]);
T = Integer.parseInt(s[2]);
map = new int[R][C];
int cleaner = -1;
for(int i=0; i<R; i++) {
s = br.readLine().split(" ");
for(int j=0; j<C; j++) {
map[i][j] = Integer.parseInt(s[j]);
if(map[i][j] == -1 && cleaner == -1) {
cleaner = i;
}
}
}
while(T-->0) {
q = new LinkedList<>();
for(int i=0; i<R; i++) {
for(int j=0; j<C; j++) {
if(map[i][j] != 0 && map[i][j] != -1) {
q.add(new Node(i,j,map[i][j]));
}
}
}
diffusion();
wind(cleaner);
}
int sum = cal();
System.out.println(sum);
}
static void diffusion() {
while(!q.isEmpty()) {
Node cur = q.poll();
int dust = cur.d/5;
int count = 0;
if(dust == 0)
continue;
for(int i=0; i<4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if(nx < 0 || nx >= R || ny<0 || ny>=C || map[nx][ny] == -1)
continue;
count++;
map[nx][ny] += dust;
}
map[cur.x][cur.y] -= dust*count;
}
}
static void wind(int cleaner) {
int up = cleaner;
int down = cleaner+1;
for(int i=up-1; i>0; i--) {
map[i][0] = map[i-1][0];
}
for(int i=0; i<C-1; i++) {
map[0][i] = map[0][i+1];
}
for(int i=0; i<up; i++) {
map[i][C-1] = map[i+1][C-1];
}
for(int i=C-1; i>1; i--) {
map[up][i] = map[up][i-1];
}
map[up][1] = 0; // ๊ณต๊ธฐ์ฒญ์ ๊ธฐ์์ ๋ฐ๋ก ๋์จ ์
for(int i=down+1; i<R-1; i++) {
map[i][0] = map[i+1][0];
}
for(int i=0; i<C-1; i++) {
map[R-1][i] = map[R-1][i+1];
}
for(int i=R-1; i>down; i--) {
map[i][C-1] = map[i-1][C-1];
}
for(int i=C-1; i>1; i--) {
map[down][i] = map[down][i-1];
}
map[down][1] = 0;
}
static int cal() {
int sum = 0;
for(int i=0; i<R; i++) {
for(int j=0; j<C; j++) {
if(map[i][j] != -1 && map[i][j] != 0)
sum += map[i][j];
}
}
return sum;
}
static class Node{
int x;
int y;
int d;
Node(int x, int y, int d){
this.x = x;
this.y = y;
this.d = d;
}
}
}
์ฑ๊ณตโจ