마법사 상어와 파이어스톰 C++

https://www.acmicpc.net/problem/20058

20058번: 마법사 상어와 파이어스톰

 

#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>

const int MAX = 65;
int a[MAX][MAX];
int visited[MAX][MAX];
int n, q, l;
int temp_num = 0;
struct Ice { int x, y; };
Ice ic[4] = { { -1,0 },{ 1,0 },{ 0,1 },{ 0,-1 } };
int pow_n;

using namespace std;

void DivideMap(int i, int j,int len) {
	int end_x, end_y;
	for (int k = 0; k < len; k++) {
		int start_x = i+k;
		int start_y = j+k;
		if (k == 0) {
			end_x = start_x + pow(2, l) - k - 1;
			end_y = start_y + pow(2, l) - k - 1;
		}
		else {
			end_x -= 1;
			end_y -= 1;
		}

		int index_i = start_x;
		int index_y = start_y;
		int tem_i = 0;
		vector <int> tem;
		for (int i = start_x; i <= end_x; i++) tem.push_back(a[i][start_y]);
		for (int j = start_y; j <= end_y; j++) a[index_i++][start_y] = a[end_x][j];
		index_i -= 1;
		for (int i = end_x; i >= start_x; i--) a[end_x][index_y++] = a[i][end_y];
		index_y -= 1;
		for (int j = end_y; j >= start_y; j--) a[index_i--][end_y] = a[start_x][j];
		for (int j = end_y; j >= start_y; j--) a[start_x][j] = tem[tem_i++];
	}
}

void ReduceIce() {

	int movei, movej;
	vector <pair<int, int>> v;

	for (int i = 1; i <= pow_n; i++) {
		for (int j = 1; j <= pow_n; j++) {
			int count = 0;
			if (a[i][j] > 0) {
				for (int k = 0; k < 4; k++) {
					movei = i + ic[k].x;
					movej = j + ic[k].y;

					if (movei > 0 && movej > 0 && movei <= pow_n && movej <= pow_n) {
						if (a[movei][movej] > 0)
							count++;
					}
				}
				if (count < 3)
					v.push_back(make_pair(i, j));
			}
		}
	}
	for (int i = 0; i < v.size(); i++) {
		a[v[i].first][v[i].second] -= 1;
	}
}

void dfs(int i, int j) {
	visited[i][j] = 1;

	for (int k = 0; k < 4; k++) {
		int movei = i + ic[k].x;
		int movej = j + ic[k].y;

		if (movei > 0 && movej > 0 && movei <= pow_n && movej <= pow_n && visited[movei][movej] != 1 && a[movei][movej] >0) {
			temp_num++;
			dfs(movei, movej);
		}
	}
}

int Find_Ice() {
	memset(visited, -1, sizeof(visited));
	int answer = 0;
	int count = 0;

	for (int i = 1; i <= pow_n; i++) {
		for (int j = 1; j <= pow_n; j++) {
			count += a[i][j];
			if (a[i][j] > 0 && visited[i][j] != 1) {
				temp_num = 1;
				dfs(i, j);
				if (temp_num > answer)
					answer = temp_num;
			}
		}
	}
	cout << count << endl;
	return answer;
}

int main(void) {
	cin >> n >> q;
	pow_n = pow(2, n);

	for (int i = 1; i <= pow_n; i++) {
		for (int j = 1; j <= pow_n; j++) {
			cin >> a[i][j];
		}
	}

	for (int i = 0; i < q; i++) {
		cin >> l;


		for (int i = 1; i <= pow_n; i+= pow(2,l)) {
			for (int j = 1; j <= pow_n; j+= pow(2,l)) {
				DivideMap(i, j,pow(2,l)/2);
			}
		}
		ReduceIce();
	}
	cout << Find_Ice() << endl;
}