[백준 14500] 테트로미노

[백준 14500] 테트로미노

문제 링크

#include "header.h"
using namespace std;
int N, M;
int paper[504][504];


void solve() {
    vector<vector<vector<pair<int, int>>>> poly = {
        {{{0, 0}, {0, 1}, {1, 0}, {1, 1}}},  //정사각형
        {
            {{0, 0}, {0, 1}, {0, 2}, {0, 3}},
            {{0, 0}, {1, 0}, {2, 0}, {3, 0}}  //길쭉
        },
        {
            {{0, 0}, {1, 0}, {1, 1}, {2, 1}},
            {{0, 0}, {0, 1}, {-1, 1}, {-1, 2}},
            {{0, 0}, {0, 1}, {-1, 1}, {1, 0}},
            {{0, 0}, {0, 1}, {1, 1}, {1, 2}}  //꽈배기
        },
        {
            {{0, 0}, {1, 0}, {2, 0}, {2, 1}},
            {{0, 0}, {0, 1}, {0, 2}, {1, 0}},
            {{0, 0}, {0, 1}, {1, 1}, {2, 1}},
            {{0, 0}, {0, 1}, {0, 2}, {-1, 2}},  //낫
            {{0, 0}, {0, 1}, {-1, 1}, {-2, 1}},
            {{0, 0}, {0, 1}, {0, 2}, {1, 2}},
            {{0, 0}, {0, 1}, {1, 0}, {2, 0}},
            {{0, 0}, {1, 0}, {1, 1}, {1, 2}}
        },
        {
            {{0, 0}, {0, 1}, {0, 2}, {-1, 1}},
            {{0, 0}, {1, 0}, {2, 0}, {1, 1}},
            {{0, 0}, {0, 1}, {0, 2}, {1, 1}},
            {{0, 0}, {0, 1}, {1, 1}, {-1, 1}}  //빠큐
        }};
    int ans = 0;
    
    for (int i = 0; i < poly.size(); i++) {  //5개의 폴리웅앵
        //j : 회전 수
        for (int j = 0; j < poly[i].size(); j++) {
            //맵 돌면서 맞춰보기
            for(int a=0; a<N; a++){
                for(int b=0; b<M; b++){

                    int cnt = 0;
                    for(int c=0; c<4; c++){
                        int nx = a + poly[i][j][c].first;
                        int ny = b + poly[i][j][c].second;

                        //범위 체크
                        if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;

                        cnt += paper[nx][ny];
                    }

                    ans = max(ans, cnt);
                }
            }
        }
    }

    cout << ans << endl;
}
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> paper[i][j];
        }
    }
}
int main() {
    input();
    solve();

    return 0;
}

• 그냥 빡구현 했다.
• 낫모양은 대칭이 있다는 것을 주의해야한다!
• dfs로 푸는 방법도 있나보다.. 찾아보자.