BOJ17144: 미세먼지 안녕!

작성일

https://www.acmicpc.net/problem/17144

  • 침착함이 중요한 시뮬레이션 문제.
  • 일단 생각한대로 풀었다는것에 만족
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
113
114
115
#include <bits/stdc++.h>
using namespace std;

struct Problem {
  int R, C, T, UH, BH;
  vector<vector<int>> room, bak;
  vector<int> dx = {-1,0,1,0};
  vector<int> dy = {0,1,0,-1};

  Problem(int r, int c, int t): room(r, vector<int>(c)) {
    R = r, C = c, T = t;
    UH = BH = 0;
  }

  bool bound(int x, int y) {
    return x >= 0 && y >= 0 && x < R && y < C;
  }

  bool boundU(int x, int y) {
    return x >= 0 && y >= 0 && x <= UH && y < C;
  }

  bool boundB(int x, int y) {
    return x >= BH && y >= 0 && x < R && y < C;
  }

  void setDust(int x, int y, int v) {
    room[x][y] = v;
    if(v == -1 && !UH) UH = x;
    else if(v == -1) BH = x;
  }

  int spread() {
    int sum = 0;
    bak = room;
    for(int x = 0; x < R; x++) {
      for(int y = 0; y < C; y++) {
        if(room[x][y] <= 0) continue;
        sum += room[x][y];
        int cnt = 0;
        for(int k = 0; k < 4; k++) {
          int nx = x + dx[k];
          int ny = y + dy[k];
          if(!bound(nx,ny)) continue;
          if(room[nx][ny] == -1) continue;
          bak[nx][ny] += room[x][y]/5;
          cnt++;
        }
        bak[x][y] -= room[x][y]/5*cnt;
      }
    }
    room = bak;
    return sum;
  }

  void print() {
    printf("\n");
    for(int i = 0; i < R; i++) {
      for(int j = 0; j < C; j++)
        printf("%3d", room[i][j]);
      printf("\n");
    }
    printf("\n");
  }

  vector<int> bx = {1,0,-1,0};
  vector<int> by = {0,1,0,-1};
  vector<int> ux = {-1,0,1,0};
  vector<int> uy = {0,1,0,-1};

  void circulate(int s, vector<int>& dx, vector<int>& dy) {
    int x = s, y = 0, i = 0;
    while(1) {
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(s == UH && !boundU(nx, ny) || s == BH && !boundB(nx, ny)) {
        i++;
        nx = x + dx[i];
        ny = y + dy[i];
      }
      swap(room[x][y], room[nx][ny]);
      x = nx, y = ny;
      if(x == s && y == 0) break;
    }
  }

  void solve() {
    int sum = 0;
    while(T--) {
      sum = spread();
      sum -= room[UH-1][0];
      sum -= room[BH+1][0];
      if(sum == 0) break;
      room[UH-1][0] = room[BH+1][0] = 0;
      circulate(UH, ux, uy);
      circulate(BH, bx, by);
    }
    cout << sum;
  }
};

int main() {
  int R, C, T, tmp;
  ios::sync_with_stdio(false);
  cin >> R >> C >> T;

  Problem prob(R,C,T);
  for(int i = 0; i < R; i++) {
    for(int j = 0; j < C; j++) {
      cin >> tmp;
      prob.setDust(i, j, tmp);
    }
  }
  prob.solve();
}