[BOJ 14500 // C++] 테트로미노

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 14500번 문제인 테트로미노이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/14500

14500번: 테트로미노

이 문제는 보드판에 격자에 맞게끔 테트로미노를 하나 놓아 해당 칸에 적힌 숫자들의 총합이 최대가 되게끔 하는 문제이다.

 

모든 테트로미노의 모양을 빠짐없이 확인하는 것이 중요한 문제이다. 아래를 펼치면 가능한 모든 테트로미노의 모양을 1로 표현해두었다. 0은 빈 공간이다.

---

1111

 

111

100

 

111

010

 

111

001

 

110

011

 

011

110

 

100

111

 

010

111

 

001

111

 

11

11

 

11

10

10

 

10

11

10

 

10

10

11

 

10

11

01

 

01

11

10

 

11

01

01

 

01

11

01

 

01

01

11

 

1

1

1

1

---

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;

int N, M;
int board[500][500];
int ans = 0;

void tetra(int i, int j) {
    int x;
    if (i + 3 < N) {
        x = board[i][j] + board[i + 1][j] + board[i + 2][j] + board[i + 3][j];
        if (ans < x) ans = x;
    }
    if (i + 2 < N and j + 1 < M) {
        x = board[i][j] + board[i + 1][j] + board[i + 2][j] + board[i][j + 1];
        if (ans < x) ans = x;
        x = board[i][j] + board[i + 1][j] + board[i + 2][j] + board[i + 1][j + 1];
        if (ans < x) ans = x;
        x = board[i][j] + board[i + 1][j] + board[i + 2][j] + board[i + 2][j + 1];
        if (ans < x) ans = x;
        x = board[i][j] + board[i + 1][j] + board[i + 1][j + 1] + board[i + 2][j + 1];
        if (ans < x) ans = x;
        x = board[i][j] + board[i][j + 1] + board[i + 1][j + 1] + board[i + 2][j + 1];
        if (ans < x) ans = x;
        x = board[i + 1][j] + board[i][j + 1] + board[i + 1][j + 1] + board[i + 2][j + 1];
        if (ans < x) ans = x;
        x = board[i + 2][j] + board[i][j + 1] + board[i + 1][j + 1] + board[i + 2][j + 1];
        if (ans < x) ans = x;
        x = board[i + 1][j] + board[i][j + 1] + board[i + 1][j + 1] + board[i + 2][j];
        if (ans < x) ans = x;
    }
    if (i + 1 < N and j + 1 < M){
        x = board[i][j] + board[i][j + 1] + board[i + 1][j] + board[i + 1][j + 1];
        if (ans < x) ans = x;
    }
    if (i + 1 < N and j + 2 < M) {
        x = board[i][j] + board[i][j + 1] + board[i][j + 2] + board[i + 1][j];
        if (ans < x) ans = x;
        x = board[i][j] + board[i][j + 1] + board[i][j + 2] + board[i + 1][j + 1];
        if (ans < x) ans = x;
        x = board[i][j] + board[i][j + 1] + board[i][j + 2] + board[i + 1][j + 2];
        if (ans < x) ans = x;
        x = board[i][j] + board[i][j + 1] + board[i + 1][j + 1] + board[i + 1][j + 2];
        if (ans < x) ans = x;
        x = board[i][j] + board[i + 1][j] + board[i + 1][j + 1] + board[i + 1][j + 2];
        if (ans < x) ans = x;
        x = board[i][j + 1] + board[i + 1][j] + board[i + 1][j + 1] + board[i + 1][j + 2];
        if (ans < x) ans = x;
        x = board[i][j + 2] + board[i + 1][j] + board[i + 1][j + 1] + board[i + 1][j + 2];
        if (ans < x) ans = x;
        x = board[i][j + 1] + board[i + 1][j] + board[i + 1][j + 1] + board[i][j + 2];
        if (ans < x) ans = x;
    }
    if (j + 3 < M) {
        x = board[i][j] + board[i][j + 1] + board[i][j + 2] + board[i][j + 3];
        if (ans < x) ans = x;
    }
}

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    int x;
    for (int i = 0;i < N;i++) {
        for (int j = 0;j < M;j++) {
            cin >> x;
            board[i][j] = x;
        }
    }
    for (int i = 0;i < N;i++) {
        for (int j = 0;j < M;j++) {
            tetra(i, j);
        }
    }

    cout << ans;

    return 0;
}