PS
14500. 테트로미노
tose33
2020. 9. 1. 20:50
https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변�
www.acmicpc.net
처음에 대충 읽고 테트로미노를 n x m 크기의 종이 위에 꽉채워서 나올수 있는 최대값을 구하는줄 알고 많이 당황했다.
다행히 그건아니고 테트로미노 중 한개를 종이위에 놓았을때 그 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 구하는 것이 었다.
일단 테트로미노는 회전이나 대칭을 시켜도 되니 모든 테트로미노를 구해봤다.
대칭 회전을 모두 고려했을때 총 19가지의 테트로미노가 있다.
for문 19개를 만들어서 각각의 for문에서 한칸씩 이동하면서 수들의 합을 구하고
가장 큰 값을 계속 갱신했다.
코드
더보기
#include <iostream>
using namespace std;
int main() {
int n, m; /* 세로 n, 가로 m */
cin >> n >> m;
int arr[501][501];
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> arr[i][j];
}
}
int sum = 0;
/* ㅁㅁㅁㅁ */
for(int i = 0; ; i++) {
if(i == n) break;
for(int j = 0; ; j++) {
if(j+3 == m) break;
sum = max(sum, arr[i][j] + arr[i][j+1] + arr[i][j+2] + arr[i][j+3]);
}
}
/* ㅁ
ㅁ
ㅁ
ㅁ */
for(int i = 0; ; i++) {
if(i+3 == n) break;
for(int j = 0; ; j++) {
if(j == m) break;
sum = max(sum, arr[i][j] + arr[i+1][j] + arr[i+2][j] + arr[i+3][j]);
}
}
/* ㅁㅁ
ㅁㅁ */
for(int i = 0; ; i++) {
if(i+1 == n) break;
for(int j = 0; ; j++) {
if(j +1 == m) break;
sum = max(sum, arr[i][j] + arr[i][j+1] + arr[i+1][j] + arr[i+1][j+1]);
}
}
/* ㅁ ㅁ ㅁ
ㅁ */
for(int i = 0; ; i++) {
if(i+1 == n) break;
for(int j = 0; ; j++) {
if(j+2 == m) break;
sum = max(sum, arr[i][j] + arr[i][j+1] + arr[i][j+2] + arr[i+1][j+1]);
}
}
/* ㅁ
ㅁ ㅁ
ㅁ */
for(int i = 0; ; i++) {
if(i+2 == n) break;
for(int j = 0; ; j++) {
if(j+1 == m) break;
sum = max(sum, arr[i][j] + arr[i+1][j] + arr[i+2][j] + arr[i+1][j+1]);
}
}
/* ㅁ
ㅁ ㅁ ㅁ */
for(int i = 0; ; i++) {
if(i+1 == n) break;
for(int j = 0; ; j++) {
if(j+2 == m) break;
sum = max(sum, arr[i][j+1] + arr[i+1][j] + arr[i+1][j+1] + arr[i+1][j+2]);
}
}
/* ㅁ
ㅁ ㅁ
ㅁ */
for(int i = 0; ; i++) {
if(i+2 == n) break;
for(int j = 0; ; j++) {
if(j+1 == m) break;
sum = max(sum, arr[i][j+1] + arr[i+1][j] + arr[i+1][j+1] + arr[i+2][j+1]);
}
}
/* ㅁ
ㅁ
ㅁ ㅁ */
for(int i = 0; ; i++) {
if(i+2 == n) break;
for(int j = 0; ; j++) {
if(j+1 == m) break;
sum = max(sum, arr[i][j] + arr[i+1][j] + arr[i+2][j] + arr[i+2][j+1]);
}
}
/* ㅁ
ㅁ ㅁ ㅁ */
for(int i = 0; ; i++) {
if(i+1 == n) break;
for(int j = 0; ; j++) {
if(j+2 == m) break;
sum = max(sum, arr[i][j+2] + arr[i+1][j] + arr[i+1][j+1] + arr[i+1][j+2]);
}
}
/* ㅁ ㅁ
ㅁ
ㅁ */
for(int i = 0; ; i++) {
if(i+2 == n) break;
for(int j = 0; ; j++) {
if(j+1 == m) break;
sum = max(sum, arr[i][j] + arr[i][j+1] + arr[i+1][j+1] + arr[i+2][j+1]);
}
}
/* ㅁ
ㅁ ㅁ ㅁ */
for(int i = 0; ; i++) {
if(i+1 == n) break;
for(int j = 0; ; j++) {
if(j+2 == m) break;
sum = max(sum, arr[i][j] + arr[i+1][j] + arr[i+1][j+1] + arr[i+1][j+2]);
}
}
/* ㅁ ㅁ
ㅁ
ㅁ */
for(int i = 0; ; i++) {
if(i+2 == n) break;
for(int j = 0; ; j++) {
if(j+1 == m) break;
sum = max(sum, arr[i][j] + arr[i][j+1] + arr[i+1][j] + arr[i+2][j]);
}
}
/* ㅁ
ㅁ
ㅁ ㅁ */
for(int i = 0; ; i++) {
if(i+2 == n) break;
for(int j = 0; ; j++) {
if(j+1 == m) break;
sum = max(sum, arr[i][j+1] + arr[i+1][j+1] + arr[i+2][j] + arr[i+2][j+1]);
}
}
/* ㅁ ㅁ ㅁ
ㅁ */
for(int i = 0; ; i++) {
if(i+1 == n) break;
for(int j = 0; ; j++) {
if(j+2 == m) break;
sum = max(sum, arr[i][j] + arr[i][j+1] + arr[i][j+2] + arr[i+1][j]);
}
}
/* ㅁ ㅁ ㅁ
ㅁ */
for(int i = 0; ; i++) {
if(i+1 == n) break;
for(int j = 0; ; j++) {
if(j+2 == m) break;
sum = max(sum, arr[i][j] + arr[i][j+1] + arr[i][j+2] + arr[i+1][j+2]);
}
}
/* ㅁ
ㅁ ㅁ
ㅁ */
for(int i = 0; ; i++) {
if(i+2 == n) break;
for(int j = 0; ; j++) {
if(j+1 == m) break;
sum = max(sum, arr[i][j] + arr[i+1][j] + arr[i+1][j+1] + arr[i+2][j+1]);
}
}
/* ㅁ ㅁ
ㅁ ㅁ */
for(int i = 0; ; i++) {
if(i+1 == n) break;
for(int j = 0; ; j++) {
if(j+2 == m) break;
sum = max(sum, arr[i][j+1] + arr[i][j+2] + arr[i+1][j] + arr[i+1][j+1]);
}
}
/* ㅁ
ㅁ ㅁ
ㅁ */
for(int i = 0; ; i++) {
if(i+2 == n) break;
for(int j = 0; ; j++) {
if(j+1 == m) break;
sum = max(sum, arr[i][j+1] + arr[i+1][j] + arr[i+1][j+1] + arr[i+2][j]);
}
}
/* ㅁ ㅁ
ㅁ ㅁ */
for(int i = 0; ; i++) {
if(i+1 == n) break;
for(int j = 0; ; j++) {
if(j+2 == m) break;
sum = max(sum, arr[i][j] + arr[i][j+1] + arr[i+1][j+1] + arr[i+1][j+2]);
}
}
cout << sum;
}