[BOJ] 4920 테트리스 게임

문제: www.acmicpc.net/problem/4920

 

 

문제 풀이:

위 순으로 각각 2, 2, 4, 4, 1가지 경우의 수가 있다.

각 경우를  vector에 넣어주고, 모든 위치에서 해당 블록들을 놓아 합을 계산했다.

 

 

소스 코드:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> P;

vector<vector<P>> blocks;
int n,arr[101][101],caseSize,answer;

void init() {
	vector<P> block;
	// 1-1
	for (int i = 0; i < 4; i++) {
		block.push_back({ 0,i });
	}
	blocks.push_back(block);
	block.clear();

	//1-2
	for (int i = 0; i < 4; i++) {
		block.push_back({ i,0 });
	}
	blocks.push_back(block);
	block.clear();

	//2-1
	block.push_back({ 0,0 });
	block.push_back({ 0,1 });
	block.push_back({ 1,1 });
	block.push_back({ 1,2 });
	blocks.push_back(block);
	block.clear();

	//2-2
	block.push_back({ 0,0 });
	block.push_back({ 1,-1 });
	block.push_back({ 1,0 });
	block.push_back({ 2,-1 });
	blocks.push_back(block);
	block.clear();

	//3-1
	block.push_back({ 0,0 });
	for (int i = 0; i < 3; i++) {
		block.push_back({ 1,-1+i });
	}
	blocks.push_back(block);
	block.clear();

	//3-2
	block.push_back({ 0,0 });
	for (int i = 0; i < 3; i++) {
		block.push_back({ -1 + i,-1 });
	}
	blocks.push_back(block);
	block.clear();

	//3-3
	block.push_back({ 0,0 });
	for (int i = 0; i < 3; i++) {
		block.push_back({ -1 ,-1+i });
	}
	blocks.push_back(block);
	block.clear();

	//3-4
	block.push_back({ 0,0 });
	for (int i = 0; i < 3; i++) {
		block.push_back({ -1 + i,+1 });
	}
	blocks.push_back(block);
	block.clear();
	
	//4
	block.push_back({ 0,0 });
	block.push_back({ 1,0 });
	block.push_back({ 0,1 });
	block.push_back({ 1,1 });
	blocks.push_back(block);
	block.clear();

	//5-1
	block.push_back({ 0,0 });
	for (int i = 0; i < 3; i++) {
		block.push_back({ -1 ,-2+i });
	}
	blocks.push_back(block);
	block.clear();

	//5-2
	block.push_back({ 0,0 });
	for (int i = 0; i < 3; i++) {
		block.push_back({-2+i,1 });
	}
	blocks.push_back(block);
	block.clear();

	//5-3
	block.push_back({ 0,0 });
	for (int i = 0; i < 3; i++) {
		block.push_back({ 1,i });
	}
	blocks.push_back(block);
	block.clear();

	//5-4
	block.push_back({ 0,0 });
	for (int i = 0; i < 3; i++) {
		block.push_back({ i,-1});
	}
	blocks.push_back(block);
	block.clear();
}
int check(int curx,int cury,int blockNum) {
	int sum=0;
	for (int i = 0; i < 4; i++) {
		int x = curx + blocks[blockNum][i].first;
		int y = cury + blocks[blockNum][i].second;
		if (x < 0 || x >= n || y < 0 || y >= n) return -100000000;
		sum += arr[x][y];
	}
	return sum;
}
void func() {
	answer = -100000000;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < caseSize; k++) {
				answer = max(answer, check(i, j, k));
			}
		}
	}
}
int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	init();
	caseSize = blocks.size();

	int testNum = 1;
	while (1) {
		cin >> n;
		if (n == 0) return 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> arr[i][j];
			}
		}
		func();
		cout << testNum << ". " << answer<<'\n';
		testNum++;
	}
	return 0;
}