BOJ 14324 - Rain (Small)

BOJ 14324 - Rain (Small)

개념 을 참고한다.

const int inf = 1e9;  
const int dy[] = {-1, 0, 1, 0}, dx[] = {0, 1, 0, -1}, op[] = {2, 3, 0, 1};  
void solve() {  
   int Y, X;  
   cin >> Y >> X;  
   vvi b(Y, vi(X));  
   auto can = b;  
   fv2(b);  
   queue<pi> q;  
   for (int y = 0; y < Y; y++)  
      for (int x = 0; x < X; x++) {  
         if (y == 0 || y == Y - 1 || x == 0 || x == X - 1) {  
            can[y][x] = b[y][x];  
            q.push({y, x});  
         } else {  
            can[y][x] = inf;  
         }  
      }  
   while (sz(q)) {  
      auto[y, x] = q.front();  
      q.pop();  
      for (int d = 0; d < 4; d++) {  
         int ny = y + dy[d], nx = x + dx[d];  
         if (ny >= 0 && ny < Y && nx >= 0 && nx < X) {  
            int h = can[y][x];  
            if (can[ny][nx] > h) {  
               can[ny][nx] = max(h, b[ny][nx]);  
               q.push({ny, nx});  
            }  
         }  
      }  
   }  
   int ans = 0;  
   for (int y = 0; y < Y; y++) for (int x = 0; x < X; x++) ans += can[y][x] - b[y][x];  
   cout << ans << endl;  
}