모노미노도미노 2 (feat. 백준, 20061번)

모노미노도미노 2
https://www.acmicpc.net/problem/20061

20061번: 모노미노도미노 2

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/20061
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int N, blue_point, green_point;
bool blue[6][4], green[6][4];
vector<int> blue_q, green_q;
inline void blue_monomino()
{
	int ix;
	if (blue_q.size() == 1) {
		for (ix = 1; ix < 5; ++ix)
			if (blue[ix + 1][blue_q[0]]) {
				blue[ix][blue_q[0]] = true, blue_q.clear();
				break;
			}
		if(ix == 5)
			blue[ix][blue_q[0]] = true, blue_q.clear();
	}
	else {
		if (blue_q[0] == blue_q[1]) {
			for (ix = 1; ix < 5; ++ix)
				if (blue[ix + 1][blue_q[0]]) {
					blue[ix - 1][blue_q[0]] = blue[ix][blue_q[1]] = true, blue_q.clear();
					break;
				}
			if (ix == 5)
				blue[ix - 1][blue_q[0]] = blue[ix][blue_q[1]] = true, blue_q.clear();
		}
		else {
			for (ix = 1; ix < 5; ++ix)
				if (blue[ix + 1][blue_q[0]] || blue[ix + 1][blue_q[1]]) {
					blue[ix][blue_q[0]] = blue[ix][blue_q[1]] = true, blue_q.clear();
					break;
				}
			if (ix == 5)
				blue[ix][blue_q[0]] = blue[ix][blue_q[1]] = true, blue_q.clear();
		}
	}
	
	for(ix = 5; ix >= 0; --ix)
		if (blue[ix][0] && blue[ix][1] && blue[ix][2] && blue[ix][3]) {
			++blue_point;
			for(auto idx = ix; idx >= 1; --idx)
				memmove(blue[idx], blue[idx - 1], 4);
			memset(blue[0], false, 4);
			++ix;
		}

	bool find = false;
	for (ix = 0; ix < 2 && !find; ++ix)
		for (auto iy = 0; iy < 4; ++iy)
			if (blue[ix][iy]) {
				find = true; break;
			}

	if (find)
		if (ix == 2)
			for (auto idx = 4; idx >= 1; --idx)
				memmove(blue[idx + 1], blue[idx], 4), memset(blue[idx], false, 4);
		else if (ix == 1)
			for (auto idx = 3; idx >= 0; --idx)
				memmove(blue[idx + 2], blue[idx], 4), memset(blue[idx], false, 4);
}
inline void green_monomino()
{
	int ix;
	if (green_q.size() == 1) {
		for (ix = 1; ix < 5; ++ix)
			if (green[ix + 1][green_q[0]]) {
				green[ix][green_q[0]] = true, green_q.clear();
				break;
			}
		if (ix == 5)
			green[ix][green_q[0]] = true, green_q.clear();
	}
	else {
		if (green_q[0] == green_q[1]) {
			for (ix = 1; ix < 5; ++ix)
				if (green[ix + 1][green_q[0]]) {
					green[ix - 1][green_q[0]] = green[ix][green_q[1]] = true, green_q.clear();
					break;
				}
			if (ix == 5)
				green[ix - 1][green_q[0]] = green[ix][green_q[1]] = true, green_q.clear();
		}
		else {
			for (ix = 1; ix < 5; ++ix)
				if (green[ix + 1][green_q[0]] || green[ix + 1][green_q[1]]) {
					green[ix][green_q[0]] = green[ix][green_q[1]] = true, green_q.clear();
					break;
				}
			if (ix == 5)
				green[ix][green_q[0]] = green[ix][green_q[1]] = true, green_q.clear();
		}
	}

	for (ix = 5; ix >= 0; --ix)
		if (green[ix][0] && green[ix][1] && green[ix][2] && green[ix][3]) {
			++green_point;
			for (auto idx = ix; idx >= 1; --idx)
				memmove(green[idx], green[idx - 1], 4);
			memset(green[0], false, 4);
			++ix;
		}

	bool find = false;
	for (ix = 0; ix < 2 && !find; ++ix)
		for (auto iy = 0; iy < 4; ++iy)
			if (green[ix][iy]) {
				find = true; break;
			}

	if (find)
		if (ix == 2)
			for (auto idx = 4; idx >= 1; --idx)
				memmove(green[idx + 1], green[idx], 4), memset(green[idx], false, 4);
		else if (ix == 1)
			for (auto idx = 3; idx >= 0; --idx)
				memmove(green[idx + 2], green[idx], 4), memset(green[idx], false, 4);
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
	blue_point = green_point = 0;
	cin >> N;
	for (int idx = 0, t, x, y; idx < N; ++idx) {
		cin >> t >> x >> y;
		if (t == 1)			blue_q.push_back(x), green_q.push_back(y);
		else if (t == 2)	blue_q.push_back(x), blue_q.push_back(x), green_q.push_back(y), green_q.push_back(y + 1);
		else				blue_q.push_back(x), blue_q.push_back(x + 1), green_q.push_back(y), green_q.push_back(y);
		blue_monomino(), green_monomino();
	}
	auto count = 0;
	for (int ix = 5, iy; ix >= 2; --ix)
		for (iy = 0; iy < 4; ++iy) {
			if (blue[ix][iy])		++count;
			if (green[ix][iy])		++count;
		}
	cout << blue_point + green_point << endl << count << endl;
	return 0;
}
// *&)*@*

1. 도미노를 놓을때는 위에서부터 내려와야 하며, 가로로 긴 1X2가 왔을때는 현재의 +행 에서의 두 열을 모두 체크해야 합니다.
2. 도미노를 놓은 뒤 한 행의 모든 열이 채워진 경우, 행이 모두 한칸씩 내려오게 되는데, 그 이후 방금 채워진 곳부터 다시 체크해야 합니다. (4번째 행이 채워진 경우, 3번째 행->4번째 행/2번째 행->3번째 행 으로 이동되므로 다시 4번째 행부터 검사해야 합니다.)