5653. 줄기세포 배양

예시를 보면 수명이 x인 줄기세포는 처음 x시간동안 비활성화 되어있고 이후 x시간동안 활성화 되어있는 것을 알 수 있다.

또한 활성화 되는 순간 상하좌우로 번식한다. 활성화 시간이 끝나면 죽은 상태로 셀을 차지하고 해당 위치로는 번식하지 못한다.

줄기세포의 수명은 1~10이고 처음 주어지는 그리드의 한 변은 1~50범위이며 시간은 최대 300까지이므로

수명이 1이고 50*50 그리드를 가득 채우고 있다고 하더라도 2시간당 사방으로 한번씩 뻗어나가므로 상하좌우 150칸까지밖에 뻗지 못한다.

따라서 

1. 맵을 넉넉하게 500*500으로 잡고 visited배열을 관리하면서 

2. 수명을 x라고 했을때 q[x].push({x*2,i,j})를 한 후 시간이 지날때마다 q.first--한 후 다시 push하고 q.first == x 된 순간 번식시키고 0이되면 push를 하지 않으며

3. 번식한 위치에서 처음 q에서 pop되었을 때 ans++, q.first == 0일 때 ans-- 하면 최종 답이 나온다.

으로 진행한다. 큐를 총 10개 쓰는 방식인 q[x] = {2*x,i,j}도 가능하고 하나만 쓰는 방식인 q = {2*x,x,i,j}도 가능하다. 취향껏 하면 된다.

같은 위치에 같은 타이밍에 번식할 경우 원래 수명이 많은 세포가 해당 자리를 차지한다는 점을 주의해야 한다.

#include <iostream>
#include <algorithm>
#include <memory.h>
#include <queue>
using namespace std;
 
#define BASE 200
 
struct p {
    int r, x, y;
};
 
int t, tc;
int N, M, K;
int map[500][500];
int dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 };
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> t;
    for (tc = 1; tc <= t; ++tc) {
        memset(map, 0, sizeof(map));
        cin >> N >> M >> K;
        // remain_time, value, x, y
        queue<p> q[11];
        int ans = 0;
        for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) {
            cin >> map[i + BASE][j + BASE];
            if (map[i + BASE][j + BASE]) {
                q[map[i + BASE][j + BASE]].push({ 2*map[i + BASE][j + BASE], i + BASE, j + BASE });
            }
        }
        int s = 0;
        for (int i = 0; i <= K; ++i) {
            for (int j = 10; j >= 1; --j) {
                int siz = q[j].size();
                for (int k = 0; k < siz; ++k) {
                    auto x = q[j].front();
                    q[j].pop();
                    if (x.r > j) {
                        if (map[x.x][x.y] > 0) {
                            ans++;
                            map[x.x][x.y] = -map[x.x][x.y];
                        }
                        q[j].push({ x.r - 1,x.x,x.y });
                    }
                    else if (x.r == j) {
                        
                        q[j].push({ j - 1,x.x,x.y });
                        for (int l = 0; l < 4; ++l) {
                            int nx = x.x + dx[l];
                            int ny = x.y + dy[l];
                            if (map[nx][ny]) continue;
                            map[nx][ny] = j;
                            q[j].push({ 2*j,nx,ny });
                        }
                    }
                    else if (j > x.r && x.r) {
                        q[j].push({ x.r - 1,x.x,x.y });
                    }
                    else
                        ans--;
                }
            }
        }
        cout << "#" << tc << " " << ans << '\n';
    }
    return 0;
}