[백준][c++]14500-테트로미노

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

14500번: 테트로미노

백준의 실버5 문제 "4920-테트리스 게임" 과 매우 유사하다.  차이점은 이 문제에서는 주어진 테트로미노를 회전뿐만 아니라 대칭도 시켜도 된다는 점이다.

 

인풋으로 주어진 숫자를 2차원 배열에 넣어주고, 순차적으로 순회를 하며 대응 가능한 모든 테트로미노를 대입해보면 쉽게 정답을 얻을 수 있다. 풀이 자체는 단순하지만, 테트로미노를 잘못 찍으면 디버깅하기가 어려우므로 신중하게 해야 한다.

각 도형별 가짓수는 다음과 같다.

1. straight tetromino/I : 작대기 2개의 형태를 가질 수 있다.
2. skew teronomino/Z &S : s자모양 2개 z자 모양 2개
3. J tetromino : 회전 , 대칭 포함하여 8가지의 모양이 가능하다.
4. T tetromino : 대칭을 해도 같기에, 회전만으로 4가지 모양이 가능하다.
5. square tetromino : 오직 한가지 형태만이 가능하다.

총 19개의 모양을 가지고 주어진 테이블에 대입하면 된다.

 

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

int n_map[501][501];

bool check(int i, int j, int n, int m)
{
	return (i >= 0 && i < n&& j >= 0 && j < m);
}

int main()
{
	int N, M;
	cin >> N >> M;
	ios::sync_with_stdio(false);
	cin.tie(0);
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> n_map[i][j];
		}
	}

	int max_val = -98765321;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			//shape 1 straight tetromino/I 작대기 2개의 형태를 가질 수 있다.
			if (check(i, j + 3, N, M))
				max_val = max(max_val, n_map[i][j] + n_map[i][j + 1] + n_map[i][j + 2] + n_map[i][j + 3]);
			if (check(i + 3, j, N, M))
				max_val = max(max_val, n_map[i][j] + n_map[i + 1][j] + n_map[i + 2][j] + n_map[i + 3][j]);


			// shape 2-1 skew tetromino/Z 와 skew tetromino/S는 엄밀히 다르다 shape2는 Z이다
			/*
			1100
			0110
			*/
			if (check(i + 1, j + 2, N, M))
				max_val = max(max_val, n_map[i][j] + n_map[i][j + 1] + n_map[i + 1][j + 1] + n_map[i + 1][j + 2]);
			/*
			0100
			1100
			1000
			*/
			if (check(i + 2, j - 1, N, M))
				max_val = max(max_val, n_map[i][j] + n_map[i + 1][j] + n_map[i + 1][j - 1] + n_map[i + 2][j - 1]);

			// shape 2-2 skew tetromino/S
			/*
			0110
			1100
			*/
			if (check(i + 1, j - 1, N, M))
				max_val = max(max_val, n_map[i][j] + n_map[i][j + 1] + n_map[i + 1][j - 1] + n_map[i + 1][j]);
			/*
			1000
			1100
			0100
			*/
			if (check(i + 2, j + 1, N, M))
				max_val = max(max_val, n_map[i][j] + n_map[i + 1][j] + n_map[i + 1][j + 1] + n_map[i + 2][j + 1]);


			//shape3-1 J미노  'ㄱ' 은 4가지 형태를 가진다. 
			/*
			1110
			0010
			0000
			*/
			if (check(i + 1, j + 2, N, M))
				max_val = max(max_val, n_map[i][j] + n_map[i][j + 1] + n_map[i][j + 2] + n_map[i + 1][j + 2]);

			/*
			0100
			0100
			1100
			*/
			if (check(i + 2, j - 1, N, M))
				max_val = max(max_val, n_map[i][j] + n_map[i + 1][j] + n_map[i + 2][j - 1] + n_map[i + 2][j]);

			/*
			1000
			1110
			0000
			*/
			if (check(i + 1, j + 2, N, M))
				max_val = max(max_val, n_map[i][j] + n_map[i + 1][j] + n_map[i + 1][j + 1] + n_map[i + 1][j + 2]);

			/*
			1100
			1000
			1000
			*/
			if (check(i + 2, j + 1, N, M))
				max_val = max(max_val, n_map[i][j] + n_map[i][j + 1] + n_map[i + 1][j] + n_map[i + 2][j]);

			//shape3-2 J미노  'ㄱ(거꾸로)' 은 4가지 형태를 가진다.(3-1의 대칭) 
			/*
			1110
			1000
			0000
			*/
			if (check(i + 1, j + 2, N, M))
				max_val = max(max_val, n_map[i][j] + n_map[i][j + 1] + n_map[i][j + 2] + n_map[i + 1][j]);

			/*
			1100
			0100
			0100
			*/
			if (check(i + 2, j + 1, N, M))
				max_val = max(max_val, n_map[i][j] + n_map[i][j + 1] + n_map[i + 1][j + 1] + n_map[i + 2][j + 1]);

			/*
			0010
			1110
			0000
			*/
			if (check(i + 1, j - 2, N, M))
				max_val = max(max_val, n_map[i][j] + n_map[i + 1][j] + n_map[i + 1][j - 1] + n_map[i + 1][j - 2]);

			/*
			1000
			1000
			1100
			*/
			if (check(i + 2, j + 1, N, M))
				max_val = max(max_val, n_map[i][j] + n_map[i + 1][j] + n_map[i + 2][j] + n_map[i + 2][j + 1]);


			//shape4 T미노 
			/*
			1110
			0100
			0000
			*/
			if (check(i + 1, j + 2, N, M))
				max_val = max(max_val, n_map[i][j] + n_map[i][j + 1] + n_map[i][j + 2] + n_map[i + 1][j + 1]);
			/*
			0100
			1100
			0100
			*/
			if (check(i + 2, j - 1, N, M))
				max_val = max(max_val, n_map[i][j] + n_map[i + 1][j - 1] + n_map[i + 1][j] + n_map[i + 2][j]);
			/*
			0100
			1110
			0000
			*/
			if (check(i + 1, j - 1, N, M) && check(i + 1, j + 1, N, M))
				max_val = max(max_val, n_map[i][j] + n_map[i + 1][j - 1] + n_map[i + 1][j] + n_map[i + 1][j + 1]);
			/*
			0100
			0110
			0100
			*/
			if (check(i + 2, j + 1, N, M))
				max_val = max(max_val, n_map[i][j] + n_map[i + 1][j] + n_map[i + 1][j + 1] + n_map[i + 2][j]);

			//shpae 5 square tetromino/O 정사삭형 1가지 변형밖에 없음
			if (check(i + 1, j + 1, N, M))
				max_val = max(max_val, n_map[i][j] + n_map[i][j + 1] + n_map[i + 1][j] + n_map[i + 1][j + 1]);
		}
	}

	cout << max_val;


	return 0;
}