백준 14500 테트로미노

문제 링크: https://www.acmicpc.net/problem/14500

14500번: 테트로미노

가능한 회전과 대칭을 고려하면 총 19가지 가능한 테트로미노의 모양이 나오고, 전체 종이를 훑으면서 가능한 칸마다 19가지 모양의 합을 구해보고, 그 합들의 최대값을 구하면 된다.

#include <bits/stdc++.h>
using namespace std;
 
int n, m, a[501][501];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> m;
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++)
        cin >> a[i][j];
 
    int ans = 0;
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) {
        if(i <= n - 4)
            ans = max(ans, a[i][j] + a[i + 1][j] + a[i + 2][j] + a[i + 3][j]);
        if(j <= m - 4)
            ans = max(ans, a[i][j] + a[i][j + 1] + a[i][j + 2] + a[i][j + 3]);
        if(i <= n - 2 && j <= m - 2)
            ans = max(ans, a[i][j] + a[i + 1][j] + a[i][j + 1] + a[i + 1][j + 1]);
        if(i <= n - 3 && j <= m - 2) {
            for(int k = 0; k < 2; k++) for(int l = 0; l < 3; l++) {
                int c = a[i][j + k] + a[i + 1][j + k] + a[i + 2][j + k];
                ans = max(ans, c + a[i + l][j + (1 - k)]);
            }
            ans = max(ans, a[i][j] + a[i + 1][j] + a[i + 1][j + 1] + a[i + 2][j + 1]);
            ans = max(ans, a[i][j + 1] + a[i + 1][j + 1] + a[i + 1][j] + a[i + 2][j]);
        }
        if(i <= n - 2 && j <= m - 3) {
            for(int k = 0; k < 2; k++) for(int l = 0; l < 3; l++) {
                int r = a[i + k][j] + a[i + k][j + 1] + a[i + k][j + 2];
                ans = max(ans, r + a[i + (1 - k)][j + l]);
            }
            ans = max(ans, a[i][j] + a[i][j + 1] + a[i + 1][j + 1] + a[i + 1][j + 2]);
            ans = max(ans, a[i + 1][j] + a[i + 1][j + 1] + a[i][j + 1] + a[i][j + 2]);
        }
    }
 
    cout << ans << '\n';
    return 0;
}