14500 테트로미노

문제링크

코드 설명

문제에 주어진 5가지 그림을 회전 및 대칭을 하면 총 19가지 모양이 나온다. 이를 모두 block배열에 넣고 전체 브루스포스로 찍어봐서 최댓값을 출력한다.

map배열에 오른쪽과 밑으로 3칸씩 (-무한)값을 넣어준다. 할당배열을 넘었을시 최댓값이 인정되지않도록 하기위하여.. 4x4배열을 기준으로 하였기때문에 최소 3칸씩 늘려주어야한다.

이방법이 맞나싶어서 여러 블로그를 보기도하였는데 dfs를이용하여 하는 방법이있긴하데 나는 19가지를 전체 구현하는게 오히려 시험장에서나 문제의도나 맞다고 생각해서 이렇게 풀었다.

소스 코드

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int map[503][503]; // 3칸씩 음수추가 해줘야하기때문
char block[19][4][5] = {
	{//1
	"1111",
	"0000",
	"0000",
	"0000"
	},
	{//2
	"1000",
	"1000",
	"1000",
	"1000"
	},
	{//3
	"1100",
	"1100",
	"0000",
	"0000"

	},
	{//4
	"1000",
	"1000",
	"1100",
	"0000"
	},
	{//5
		"1110",
		"1000",
		"0000",
		"0000",
	},
		{//6
		"1100",
		"0100",
		"0100",
		"0000",
	},	
	{//7
		"0010",
		"1110",
		"0000",
		"0000",
	},
		{//8
		"0100",
		"0100",
		"1100",
		"0000",
	},
		{//9
		"1000",
		"1110",
		"0000",
		"0000",
	},
		{//10
		"1100",
		"1000",
		"1000",
		"0000",
	},
		{//11
		"1110",
		"0010",
		"0000",
		"0000",
	},
		{//12
		"1000",
		"1100",
		"0100",
		"0000",
	},
		{//13
		"0110",
		"1100",
		"0000",
		"0000",
	},
		{//14
		"0100",
		"1100",
		"1000",
		"0000",
	},
		{//15
		"1100",
		"0110",
		"0000",
		"0000",
	},
		{//16
		"1110",
		"0100",
		"0000",
		"0000",
	},
		{//17
		"0100",
		"1100",
		"0100",
		"0000",
	},
		{//18
		"0100",
		"1110",
		"0000",
		"0000",
		},

			{//19
		"1000",
		"1100",
		"1000",
		"0000",
			}



};

int N, M;
int get_count(int dy, int dx, int dk) {
	int ans = 0;
	for (int y = 0; y < 4; y++) {
		for (int x = 0; x < 4; x++) {
			ans += (map[dy+y][dx+x] * (block[dk][y][x] - '0'));
		}
	}
	return ans;
}
int main() {
	cin >> N >> M;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> map[y][x];
		}
	}
	for (int y = N; y <= N + 3; y++) {
		for (int x = M; x <= M + 3; x++) {
			map[y][x] = -100000;
		}
	}
	int sum = 0;
	int ans = 0;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			for (int k = 0; k < 19; k++) {
				sum=get_count(y, x,k);
				if (sum > ans) ans = sum;
			}
		}
	}
	
	cout << ans;


	return 0;
}