[BOJ] 10711. 모래성

*가장자리는 항상 모래가 있는 부분이기 때문에 1,1 ~ h-1,w-1 의 부분 중 8방향을 살펴봤을 때 '.' 인 부분이 자기 자신보다 많은 경우만 큐에 넣는다. 

즉, 큐에는 이제 사라질 좌표들만 넣는다. 

 

*큐에는 파도에 휩쓸려 사라질 부분들만 넣어지기 때문에 이 부분을 기준으로 

주변에 있는 성들을 탐색하면 된다. 

 

*더 이상 큐에 넣을게 없으면 (= 없어질 게 없으면) 종료 

 

 

?

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

#include <iostream> #include <vector> #include <queue>   using namespace std;   int h, w; char map[1001][1001]; bool visited[1001][1001]; int age[1001][1001];   typedef pair<int, int> pp; typedef pair<pp, int> ppp;   int dx[8] = { -1, -1, -1, 0, 0, 1, 1, 1 }, dy[8] = { -1, 0, 1, -1, 1, -1, 0, 1 }; queue<pp> q;     int main() {     ios_base::sync_with_stdio(false);     cin.tie(0);       cin >> h >> w;       for (int i = 0; i < h; i++)     {         for (int j = 0; j < w; j++)         {             cin >> map[i][j];         }     }       for (int i = 1; i < h - 1; i++)     {         for (int j = 1; j < w - 1; j++)         {             for (int d = 0; d < 8; d++)             {                 int nx = i + dx[d];                 int ny = j + dy[d];                   if (map[nx][ny] == '.')                 {                     age[i][j]++;                 }             }             if (map[i][j] != '.' && age[i][j] >= map[i][j] - '0') {                 q.push(pp(i, j));             }         }     }     int cnt = 1;     while (!q.empty()) {         int size = q.size();         while (size--) {             int x = q.front().first;             int y = q.front().second;             q.pop();               for (int i = 0; i < 8; i++) {                 int nx = x + dx[i];                 int ny = y + dy[i];                   if (map[nx][ny] == '.') continue;                   age[nx][ny]++;                 if (map[nx][ny] - '0' == age[nx][ny]) {                     q.push(pp(nx, ny));                 }             }         }         cnt++;     }       cout << cnt-1 << '\n';     return 0; }