줄기세포

#include <iostream>
#include <string.h>
#define f(i, n) for(int i = 0 ;  i < (n); ++i)
using namespace std;
int T, tc, R, C, K;
int lf[2][650][650], rm[2][650][650], st[2][650][650];	// 초기화완료
bool sd;

// dfs1
int vst1[650][650], v;
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };
int rb, cb;	// 초기화 완료
void dfs1(int r, int c) {
	vst1[r][c] = v;
	rm[!sd][r][c] = rm[sd][r][c] - 1;	// 수명 감소
	if (rm[sd][r][c] == 0 && st[sd][r][c] != 2) {	// 잔여 수명 0이면
		rm[!sd][r][c] = lf[sd][r][c];				// 상태 변화
		st[!sd][r][c] = st[sd][r][c] + 1;
	}
	if (st[sd][r][c] != 2) 
		rb = r, cb = c;
	f(d, 4) {
		int nr = r + dr[d], nc = c + dc[d];
		if (vst1[nr][nc] == v) continue;
		if (!lf[sd][nr][nc]) {	// 빈칸 
			if (st[sd][r][c] == 1) {	// 내가 활성 -> 번식 가능
				if (!lf[!sd][nr][nc]) {	// 내가 처음으로 번식
					lf[!sd][nr][nc] = rm[!sd][nr][nc] = lf[sd][r][c];
				}
				else if(lf[sd][r][c] > lf[!sd][nr][nc]){
					lf[!sd][nr][nc] = rm[!sd][nr][nc] = lf[sd][r][c];
				}
			}
		}
		else {				// 빈칸 아님
			if (st[sd][nr][nc] != 2) dfs1(nr, nc);
		}
	}
}

// dfs2
int vst2[650][650]; // tc 연동
int cs;
void dfs2(int r, int c) {
	vst2[r][c] = tc;
	++cs;
	f(d, 4) {
		int nr = r + dr[d], nc = c + dc[d];
		if (!lf[sd][nr][nc]) continue;	// 빈칸은 세지 않음
		if (st[sd][nr][nc] == 2) continue; // 죽은 세포는 세지 않음
		if (vst2[nr][nc] == tc) continue;	// 이미 센 세포는 세지 않음
		dfs2(nr, nc);
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> T;
	for (tc = 1; tc <= T; ++tc) {
		memset(lf, 0, sizeof(int) * 2 * 650 * 650);
		memset(rm, 0, sizeof(int) * 2 * 650 * 650);
		memset(st, 0, sizeof(int) * 2 * 650 * 650);

		cin >> R >> C >> K;
		f(r, R) f(c, C) {
			int l; cin >> l;
			lf[0][r + 300][c + 300] = rm[0][r + 300][c + 300] = l;
		}

		sd = 0;
		rb = 300, cb = 300;
		f(k, K) {
			++v;
			memcpy(lf[!sd], lf[sd], sizeof(int) * 650 * 650);
			dfs1(rb, cb);
			sd = !sd;
		}

		cs = 0;
		dfs2(rb, cb);
		cout << '#' << tc << ' ' << cs << '\n';
	}
	return 0;
}