[삼성] 마법사상어와 파이어스톰

문제 요약

환경, 초기값

• 2^N*2^N (단, N<=6) 크기의 격자에서 상어가 마법을 부립니다.
• Q(단,Q<=1000)개의 L이 주어집니다.
• Q번 마법을 부린 후를 시뮬레이션 하세요.

1번의 마법

1. L에 대해서 2^L*2^L 사이즈로 격자를 잘라서 각 파츠마다 시계방향으로 90도 회전시킵니다.
2. 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어듭니다.

결과값

1. 남아있는 얼음의 합
2. 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수

아이디어

정직한 시뮬레이션
결과값 2 때문에 bfs도 함께 구현했다.

주의할 점 1. 1번의 마법중 원본이 변형된 상태에서 아래쪽의 연산을 하지 말기 => copy

1. 커널 사이즈만큼 로테이션을 할 때, 0행이 -1열이 되었는데 1행을 -2열에 저장하려고 할 때 [0][-1]자리의 값이 변형이되어있다.
2. 얼음이 녹을 때, 방금 녹인 곳 때문에 옆자리를 녹여야한다고 착각하는 것에 주의해야한다.(아래는 틀린 예)
   

코드

소요시간 : 1시간 10분

#include<iostream>
#include<math.h>
#include<queue>
using namespace std;
int arr[64][64];
int temp[64][64];
int N;
int lim;//N에 대한 사이즈

void rot_ker(int si, int sj,int sz) {
	//temp 전체에 오리지널을 복사
	for (int i = 0; i < sz; i++) {
		for (int j = 0; j < sz; j++) {
			arr[si+j][sj + sz - 1 - i] = temp[si+i][sj+j];
		}
	}
	//cout << si << "," << sj << "," << sz << endl;
	//print_arr(-1);
}

void rot(int L) {
	int sz = pow(2, L);
	copy(&arr[0][0], &arr[0][0] + 64 * 64, &temp[0][0]);
	for(int si = 0;si<lim;si+=sz){
		for (int sj = 0; sj < lim; sj += sz) {
			rot_ker(si, sj,sz);
		}
	}
}


bool in_box(int i, int j) {
	return i >= 0 && i < lim&& j >= 0 && j < lim;
}

int di[] = { -1,1,0,0 };
int dj[] = { 0,0,-1,1 };
void down_ice() {
	copy(&arr[0][0], &arr[0][0] + 64 * 64, &temp[0][0]);
	for (int i = 0; i < lim; i++) {
		for (int j = 0; j < lim; j++) {
			//target = arr[i][j]
			int sum_ice = 0;
			for (int k = 0; k < 4; k++) {
				int fi = i + di[k], fj = j + dj[k];
				if (in_box(fi, fj)&&temp[fi][fj]>0) {
					sum_ice++;
				}
			}
			if (sum_ice < 3) {
				arr[i][j] = max(temp[i][j] - 1, 0);
			}
		}
	}
}
bool visited[64][64] = { false, };
struct pos {
	int i, j;
	pos(int ii, int jj) {
		i = ii; j = jj;
	}
};
pos get_seed() {
	for (int i = 0; i < lim; i++) {
		for (int j = 0; j < lim; j++) {
			if (visited[i][j] == false&&arr[i][j]>0) {
				return pos(i, j);
			}
		}
	}
	return pos(-1, -1);
}

int main() {
	int Q;
	int queries[1000];
	cin >> N>>Q;

	lim = pow(2, N);
	for (int i = 0; i < lim; i++) {
		for (int j = 0; j < lim; j++) {
			cin >> arr[i][j];
		}
	}
	for (int ctr = 0; ctr < Q; ctr++) {
		cin >> queries[ctr];
		rot(queries[ctr]);
		down_ice();
	}
	//bfs
	pos seed = get_seed();
	int max_con = 0;
	while (seed.i != -1) {
		int cur_con = 0;
		queue<pos> q;
		q.push(seed);
		visited[seed.i][seed.j] = true;
		cur_con++;
		while (!q.empty()) {
			pos cur = q.front();
			q.pop();

			for (int k = 0; k < 4; k++) {
				pos child = pos(cur.i + di[k], cur.j + dj[k]);
				if (in_box(child.i,child.j)&&!visited[child.i][child.j]&&arr[child.i][child.j]>0) {
					q.push(child);
					visited[child.i][child.j] = true;
					cur_con++;
				}
			}
		}
		max_con = max(max_con, cur_con);
		seed = get_seed();
	}
	int sum_ice = 0;
	for (int i = 0; i < lim; i++) {
		for (int j = 0; j < lim; j++) {
			sum_ice+=arr[i][j];
		}
	}
	cout << sum_ice << endl;
	cout << max_con << endl;
}