알고리즘/시뮬레이션
[백준] 14500-테트로미노(C++)
잉읭응
2020. 4. 14. 17:27
반응형
문제출처:https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누
www.acmicpc.net
시뮬레이션문제입니다.
차근차근 하나의 도형의 경우를 수를 적용해보셔야 합니다.
반복문 작성시 매번 테스트케이스를 입력해보면서 조기에 오류를 찾아야합니다...
다 작성하고 예외를 찾으려고 하면 절대 못찾아요....
주의하셔야 할 조건은 회전이나 대칭을 시켜도 된다 입니다.
1번 도형같은 경우에는 2가지 모양이 나옵니다.
한가지 좌우로 대칭하고 돌려도 한가지 모양만 나옵니다.
제일 괴랄한 모양으로 돌리고 대칭함으로써 총 8가지의 모양이 나옵니다.
대칭과 회전시 중복하는 모양이 생기기때문에 총 4가지 모양이 나옵니다.
역시 대칭과 회전시 중복하는 모양이 생기기때문에 총 4가지 모양이 나옵니다.
아래는 정답코드입니다.
코드확인해 보시고 꼭 직접 작성해서 풀어보세요 :)
#include <iostream>
using namespace std;
/*
1번은 회전이 가능한 4가지 경우 -> 아래 오른쪽만 해주면 됨
3번 부터는 회전이나 대칭을 시키는게 가능하기에 각 8가지
*/
int n = 0, m = 0, result = 0;
int arr[501][501] = { 0 };
void num1() {
for (int i = 0; i < n; i++)
for (int j = 0; j <= m - 4; j++)
if ((arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i][j + 3]) > result) result = (arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i][j + 3]);
for (int i = 0; i < m; i++)
for (int j = 0; j <= n - 4; j++)
if ((arr[j][i] + arr[j + 1][i] + arr[j + 2][i] + arr[j + 3][i]) > result) result = (arr[j][i] + arr[j + 1][i] + arr[j + 2][i] + arr[j + 3][i]);
}
void num2() {
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < m - 1; j++)
if ((arr[i][j] + arr[i][j + 1] + arr[i + 1][j] + arr[i + 1][j + 1]) > result) result = (arr[i][j] + arr[i][j + 1] + arr[i + 1][j] + arr[i + 1][j + 1]);
}
void num3() {
// 기본 모양
for (int i = 0; i < m - 1; i++)
for (int j = 0; j <= n - 3; j++)
if ((arr[j][i] + arr[j + 1][i] + arr[j + 2][i] + arr[j + 2][i + 1]) > result) result = (arr[j][i] + arr[j + 1][i] + arr[j + 2][i] + arr[j + 2][i + 1]);
// 기본 대칭
for (int i = 1; i < m; i++)
for (int j = 0; j <= n - 3; j++)
if ((arr[j][i] + arr[j + 1][i] + arr[j + 2][i] + arr[j + 2][i - 1]) > result) result = (arr[j][i] + arr[j + 1][i] + arr[j + 2][i] + arr[j + 2][i - 1]);
//위로 90도
for (int i = 1; i < n; i++)
for (int j = 0; j <= m - 3; j++)
if ((arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i - 1][j + 2]) > result) result = (arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i - 1][j + 2]);
//위로 90도 대칭
for (int i = 0; i < n - 1; i++)
for (int j = 0; j <= m - 3; j++)
if ((arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i + 1][j + 2]) > result) result = (arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i + 1][j + 2]);
// 위로 180도
for (int i = 2; i < n; i++)
for (int j = 1; j < m; j++)
if ((arr[i][j] + arr[i - 1][j] + arr[i - 2][j] + arr[i - 2][j - 1]) > result) result = (arr[i][j] + arr[i - 1][j] + arr[i - 2][j] + arr[i - 2][j - 1]);
// 위로 180도 대칭
for (int i = 2; i < n; i++)
for (int j = 0; j < m - 1; j++)
if ((arr[i][j] + arr[i - 1][j] + arr[i - 2][j] + arr[i - 2][j + 1]) > result) result = (arr[i][j] + arr[i - 1][j] + arr[i - 2][j] + arr[i - 2][j + 1]);
// 위로 270도
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < m - 2; j++)
if ((arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i + 1][j]) > result) result = (arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i + 1][j]);
// 위로 270도 대칭
for (int i = 1; i < n; i++)
for (int j = 0; j < m - 2; j++)
if ((arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i - 1][j]) > result) result = (arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i - 1][j]);
}
void num4() {
// 원래
for (int i = 0; i < n - 2; i++)
for (int j = 0; j < m - 1; j++)
if ((arr[i][j] + arr[i + 1][j] + arr[i + 1][j + 1] + arr[i + 2][j + 1]) > result) result = (arr[i][j] + arr[i + 1][j] + arr[i + 1][j + 1] + arr[i + 2][j + 1]);
//원래 대칭
for (int i = 0; i < n - 2; i++)
for (int j = 1; j < m; j++)
if ((arr[i][j] + arr[i + 1][j] + arr[i + 1][j - 1] + arr[i + 2][j - 1]) > result) result = (arr[i][j] + arr[i + 1][j] + arr[i + 1][j - 1] + arr[i + 2][j - 1]);
//위로 90도
for (int i = 1; i < n; i++)
for (int j = 0; j < m - 2; j++)
if ((arr[i][j] + arr[i][j + 1] + arr[i - 1][j + 1] + arr[i - 1][j + 2]) > result) result = (arr[i][j] + arr[i][j + 1] + arr[i - 1][j + 1] + arr[i - 1][j + 2]);
//위로 90도 대칭
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < m - 2; j++)
if ((arr[i][j] + arr[i][j + 1] + arr[i + 1][j + 1] + arr[i + 1][j + 2]) > result) result = (arr[i][j] + arr[i][j + 1] + arr[i + 1][j + 1] + arr[i + 1][j + 2]);
}
void num5() {
// ㅜ
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < m - 2; j++)
if ((arr[i][j] + arr[i][j + 1] + arr[i + 1][j + 1] + arr[i][j + 2]) > result) result = (arr[i][j] + arr[i][j + 1] + arr[i + 1][j + 1] + arr[i][j + 2]);
// ㅗ
for (int i = 1; i < n; i++)
for (int j = 0; j < m - 2; j++)
if ((arr[i][j] + arr[i][j + 1] + arr[i - 1][j + 1] + arr[i][j + 2]) > result) result = (arr[i][j] + arr[i][j + 1] + arr[i - 1][j + 1] + arr[i][j + 2]);
// ㅏ
for (int i = 0; i < n - 2; i++)
for (int j = 0; j < m - 1; j++)
if ((arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 1][j + 1]) > result) result = (arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 1][j + 1]);
// ㅓ
for (int i = 0; i < n - 2; i++)
for (int j = 1; j < m; j++)
if ((arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 1][j - 1]) > result) result = (arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 1][j - 1]);
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> arr[i][j];
num1();
num2();
num3();
num4();
num5();
cout << result << "\n";
}반응형