백준 14500 테트로미노

이 문제는 해당판에 주어진 5개의 테트로미노를 회전,대칭을 포함해서 놓았을때 가장 큰 값을 구하는 문제입니다.

원하는 테트로미노 모양마다 각칸에 넣어보면 되는 브루트 포스 문제입니다. 그렇다면 존재하는 모든 테트로미노의 모양을 구하는게 핵심인데 ㅗ ㅓ ㅏ ㅜ 이모양 말고는 dfs로 만들 수 있습니다. 그런데 사실 모든 경우를 따져봐도 19가지? 정도가 나와서 저는 그냥 모든 모양을 다 넣었습니다. 문제의 의도는 dfs를 이용하는 것이겠지만 그냥 뭐 이렇게 해도 풀리긴 합니다~. 물론 모양이 더많아지면 이렇게 하면 너무 힘들겠죠,,

 

다음은 코드입니다.

 

#include <bits/stdc++.h>

using namespace std;

int board[510][510];

int one[2][4][4] = {
    {
        1,1,1,1,
        0,0,0,0,
        0,0,0,0,
        0,0,0,0
    },
    {
        1,0,0,0,
        1,0,0,0,
        1,0,0,0,
        1,0,0,0
    }
};

int two[2][2] = {
    1,1,
    1,1
};

int three[8][3][3] {
    {
        1,0,0,
        1,0,0,
        1,1,0
    },
    {
        1,1,1,
        1,0,0,
        0,0,0
    },
    {
        1,1,1,
        0,0,1,
        0,0,0
    },
    {
        0,1,0,
        0,1,0,
        1,1,0
    },
    {
        1,1,0,
        0,1,0,
        0,1,0
    },
    {
        1,1,0,
        1,0,0,
        1,0,0
    },
    {
        1,0,0,
        1,1,1,
        0,0,0
    },
    {
        0,0,1,
        1,1,1,
        0,0,0
    }
};

int four[4][3][3] {
    {
        1,0,0,
        1,1,0,
        0,1,0
    },
    {
        0,1,0,
        1,1,0,
        1,0,0
    },
    {
        0,1,1,
        1,1,0,
        0,0,0
    },
    {
        1,1,0,
        0,1,1,
        0,0,0
    }
};

int five[4][3][3] {
    {
        1,1,1,
        0,1,0,
        0,0,0
    },
    {
        1,0,0,
        1,1,0,
        1,0,0
    },
    {
        0,1,0,
        1,1,1,
        0,0,0
    },
    {
        0,1,0,
        1,1,0,
        0,1,0
    }
};

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int N,M; cin >> N >> M;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++)
            cin >> board[i][j];
    int ans = 0;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++) {

            for(int k = 0; k < 2; k++) {
                int cursum = 0;
                for(int m = 0; m < 4; m++)
                    for(int l = 0; l < 4; l++) {
                        int curx = i+m;
                        int cury = j+l;

                        if(curx < 0 || curx > N-1 || cury < 0 || cury > M-1 || one[k][m][l] == 0) continue;
                        cursum += board[curx][cury];
                    }
                ans = max(ans, cursum);
            }


            int cursum = 0;
            for(int m = 0; m < 2; m++)
                for(int l = 0; l < 2; l++) {
                    int curx = i+m;
                    int cury = j+l;

                    if(curx < 0 || curx > N-1 || cury < 0 || cury > M-1 || two[m][l] == 0) continue;
                    cursum += board[curx][cury];
            }
            ans = max(ans, cursum);


            for(int k = 0; k < 16; k++) {
                int cursum = 0;
                for(int m = 0; m < 3; m++)
                    for(int l = 0; l < 3; l++) {
                        int curx = i+m;
                        int cury = j+l;

                        if(curx < 0 || curx > N-1 || cury < 0 || cury > M-1) continue;
                        if(k<8 && three[k][m][l] == 0) continue;
                        else if(k >= 8 && k < 12 && four[k%4][m][l] == 0) continue;
                        else if(k >= 12 && k < 16 && five[k%4][m][l] == 0) continue;

                        cursum += board[curx][cury];
                    }
                ans = max(ans, cursum);
            }

        }
    cout<<ans;
    return 0;
}