백준 14500번(테트로미노) c++ 풀이

https://www.acmicpc.net/problem/14500

 

테트로미노 5가지. 회전, 대칭시킨 것도 고려해야 한다.

테트로미노는 블럭 4개로 이루어져있고 종류도 5개라서 그냥 dx dy로 하드코딩했다..

4개 이상으로 만든 폴리오미노 문제가 있다면 이 방법은 번거로울 것 같다.

근데 뭐.. 이건 되니깐

 

테트로미노를 이리저리 회전, 대칭 시키는 것보다 보드를 움직이는 게 더 쉬울 것 같았다.

검은 점이 0, 0이라고 생각하면 보드는 회전/대칭하여 총 8가지의 형태가 가능

 

원본 배열을 이리저리 조작해서 새로 만드는 것보다 입력받을 때 채워넣었다..

 

나머지는 뭐 단순연산이니까..

 

#include <iostream>

using namespace std;

int n, m;
int board[8][500][500];
int ans;

// 테트로미노
int tdx[5][4] = {
    {0, 0, 0, 0},
    {0, 0, 1, 1},
    {0, 1, 2, 2},
    {0, 1, 1, 2},
    {0, 0, 0, 1},
};
int tdy[5][4] = {
    {0, 1, 2, 3},
    {0, 1, 0, 1},
    {0, 0, 0, 1},
    {0, 0, 1, 1},
    {0, 1, 2, 1},
};

int findMax(int bIdx, int tIdx){
    int xLimit = (bIdx < 4 ? n : m);
    int yLimit = (bIdx < 4 ? m : n);
    
    int maxValue = -1;
    
    for(int i=0; i<xLimit; i++){
        for(int j=0; j<yLimit; j++){
            
            int sum = 0;
            bool ok = true;
            
            for(int k=0; k<4; k++){
                int currX = i + tdx[tIdx][k];
                int currY = j + tdy[tIdx][k];
                
                if(currX < 0 || currX >= xLimit || currY < 0 || currY >= yLimit){
                    ok = false;
                    break;
                }
                
                sum += board[bIdx][currX][currY];
            }
            
            if(!ok) continue;
            
            maxValue = max(maxValue, sum);
        }
    }
    
    return maxValue;
}

void solve(){
    for(int i=0; i<8; i++){
        for(int j=0; j<5; j++){
            ans = max(ans, findMax(i, j));
        }
    }
    
    return;
}

int main(){
    cin >> n >> m;
    
    int num;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> num;
            
            board[0][i][j] = num;
            board[1][i][m - 1 - j] = num;
            board[2][n - 1 - i][j] = num;
            board[3][n - 1 - i][m - 1 - j] = num;
            
            board[4][j][i] = num;
            board[5][j][n - 1 - i] = num;
            board[6][m - 1 - j][i] = num;
            board[7][m - 1 - j][n - 1 - i] = num;
        }
    }
    
    solve();
    
    cout << ans;
    
    return 0;
}