[백준/BOJ] 백준 14500번 : 테트로미노

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

14500번: 테트로미노

각 칸마다 주어진 5개의 테트로미노를 이용해 만들어질 수 있는 모든 모양을 고려해 그중 칸에 쓰인 수들의 합이 가장 큰 값을 찾는다.

 

코드

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

int n, m;
int board[500][500];

int block[19][4][2] = {
	{ {0,0},{0,1},{0,2},{0,3} }, //a번 블록
	{ {0,0},{1,0},{2,0},{3,0} }, //a번 블록을 시계방향 1번 회전
	{ {0,0},{0,1},{1,0},{1,1} }, //b번 블록
	{ {0,0},{1,0},{2,0},{2,1} }, //c번 블록
	{ {0,0},{0,1},{0,2},{1,0} }, //c번 블록 시계방향 1번 회전
	{ {0,0},{0,1},{1,1},{2,1} }, //c번 블록 시계방향 2번 회전
	{ {0,0},{1,0},{1,-1},{1,-2} }, //c번 블록 시계방향 3번 회전
	{ {0,0},{0,1},{-1,1},{-2,1} }, //대칭c번 블록
	{ {0,0},{1,0},{1,1},{1,2} }, //대칭c번 블록 시계방향 1번 회전
	{ {0,0},{0,1},{1,0},{2,0} }, //대칭c번 블록 시계방향 2번 회전
	{ {0,0},{0,1},{0,2},{1,2} }, //대칭c번 블록 시계방향 3번 회전
	{ {0,0},{1,0},{1,1},{2,1} }, //d번 블록 
	{ {0,0},{0,1},{1,0},{1,-1} }, //d번 블록 시계방향 1번 회전
	{ {0,0},{1,0},{1,-1},{2,-1} }, //대칭d번 블록 
	{ {0,0},{0,1},{1,1},{1,2} }, //대칭d번 블록 시계방향 1번 회전
	{ {0,0},{0,1},{0,2},{1,1} }, //e번 블록
	{ {0,0},{1,0},{2,0},{1,-1} }, //e번 블록 시계방향 1번 회전
	{ {0,0},{1,0},{1,-1},{1,1}}, //e번 블록 시계방향 2번 회전
	{ {0,0},{1,0},{2,0},{1,1} } //e번 블록 시계방향 3번 회전
};

//(x,y)지점을 기준으로 해당 블록이 놓인 칸의 수들의 합을 구한다
int sum(int check_block[4][2],int x,int y)
{
	int ret = 0;

	//1x1블록이 4개가 붙어 있는것이므로 1X1블록 하나 하나 확인한다
	for (int i = 0; i < 4; i++)
	{
		//범위를 넘어갔을때
		if (x + check_block[i][0] < 0 || x + check_block[i][0] >= n || y + check_block[i][1] < 0 || y + check_block[i][1] >= m)
		{
			ret = 0;
			break;
		}

		ret += board[x + check_block[i][0]][y + check_block[i][1]];
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int max_result = 0;

	cin >> n >> m;

	for(int i=0; i<n; i++)
		for (int j = 0; j < m; j++)
			cin >> board[i][j];
	

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			for (int k = 0; k < 19; k++) //블록이 나올 수 있는 모양 13개를 각 칸마다 모두 확인한다
				max_result = max(max_result, sum(block[k], i, j));

	cout << max_result;

	return 0;
}