시간초과) 5653 줄기세포 배양

#include <stdio.h>
#include <memory>
#include <string.h>
#include <utility>
 
using namespace std;
 
int dead = -10000000;
int cur[800][800];
int power[800][800];
int tmp_power[800][800];
int cen_x = 400, cen_y = 400;
int n, m, k;
 
int bfs();
void time_later();
void spread();
int count();
 
int main() {
    int t;
    scanf("%d", &t);
 
    for (int test = 1; test <= t; test++) {
        memset(cur, 0, sizeof(cur));
        memset(power, 0, sizeof(power));
        scanf("%d %d %d", &n, &m, &k);
 
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < m; j++) {
                scanf("%d", &cur[cen_y + i][cen_x + j]);
                power[cen_y + i][cen_x + j] = cur[cen_y + i][cen_x + j];
            }
            
        int rst = bfs();
        printf("#%d %d\n", test, rst);
    }
}
 
void time_later() {
    for (int i = cen_y - k-1; i <= cen_y + n+k+1; i++) {
        for (int j = cen_x - k-1; j <= cen_x + m+k+1; j++) {
            if (cur[i][j] >= 1) {
                cur[i][j]--;
 
                if (cur[i][j] == 0)
                    cur[i][j] = - power[i][j];
            }
            else if ((cur[i][j] <= -1) && (cur[i][j] > dead)) {
                cur[i][j]++;
 
                if (cur[i][j] == 0)
                    cur[i][j] = dead;
            }
        }
    }
}
 
int bfs() {
    for (int i = 1; i <= k; i++) {        
        time_later();
 
        if (i == k)
            return count();
        
        spread();
    }
}
 
int count() {
    int cnt = 0;
    for (int i = cen_y - k - 1; i <= cen_y + n + k + 1; i++) 
        for (int j = cen_x - k - 1; j <= cen_x + m + k + 1; j++) 
            if (cur[i][j] != 0 && cur[i][j] != dead)
                cnt++;
        
    return cnt;
}
 
void spread() {
    int _dx[4] = { 1,-1,0,0 };
    int _dy[4] = { 0,0,1,-1 };
    
    memcpy(tmp_power, power, sizeof(power));
    
    for (int i = cen_y - k - 1; i <= cen_y + n + k + 1; i++) 
        for (int j = cen_x - k - 1; j <= cen_x + m + k + 1; j++) 
            if ((cur[i][j] <= -1) && (cur[i][j] > dead)) {
                for (int idx = 0; idx < 4; idx++) {
                    int dx = _dx[idx];
                    int dy = _dy[idx];
 
                    if (power[i + dy][j + dx] == 0) {
                        if (cur[i + dy][j + dx] < power[i][j] + 1) {
                            cur[i + dy][j + dx] = power[i][j] + 1;                            
                            tmp_power[i + dy][j + dx] = power[i][j];
                        }
                    }
                }
            }
 
    memcpy(power, tmp_power, sizeof(tmp_power));
}