[백준] 14500번 테트로미노(C++)

14500번: 테트로미노 (acmicpc.net)

14500번: 테트로미노

---

난이도 : 골드5

 

풀이과정 :

완전 탐색 문제이다.

모든 경우의 수.. 회전.. 대칭 에 대한 모든 경우의 수를 따져주면된다.

기존 좌표가 (x,y) 라 할때 나올수 있는 회전, 대칭에 대한 경우의 수는 8개

(x,y), (x,-y), (-x,y), (-x,-y), (y,x), (y,-x), (-y,x), (-y,-x)  다음과 같다..!!! 중딩때 배우던가... 이거

rx배열은 부호곱해줘야되서 선언해줬다.

이 걸 이용해서 dx, dy 설정해둔다음 나올 수있는 경우를 반복문으로 만들어주면된다.

코드가 굉장히  반복문이 많은데.. n, m 이 최대  500이고 테트로미노가 5개뿐이라 시간초과는 안난다.

 

 

코드 :

#include <iostream>
#include <algorithm> 
using namespace std;

int dx[5][4] = {
    {0,0,0,0}, //파
    {0, 0, 1, 1}, //노
    {0, 1, 2, 2}, //주
    {0,1,1,2}, //초
    {0,0,0,1} //핑
};
int dy[5][4] = {
    {0, 1, 2, 3},
    {0, 1, 0, 1},
    {0,0,0,1},
    {0,0,1,1},
    {0,1,2,1}
};

int rx[4] = { 1, -1, 1, -1 };
int ry[4] = { 1, 1, -1, -1 };
int n, m, arr[500][500], ans;

int cal1(int x, int y) {
    int num = 0;
    for (int k = 0; k < 4; k++) {
        for (int i = 0; i < 5; i++) {
            int cnt = 0;
            for (int j = 0; j < 4; j++) {
                int nx = x + dx[i][j] * rx[k];
                int ny = y + dy[i][j] * ry[k];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
                    cnt = 0;
                    break;
                }
                else {
                    cnt += arr[nx][ny];
                }
            }
            num = max(num, cnt);
            cnt = 0;
            for (int j = 0; j < 4; j++) {
                int nx = x + dy[i][j] * rx[k];
                int ny = y + dx[i][j] * ry[k];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
                    cnt = 0;
                    break;
                }
                else {
                    cnt += arr[nx][ny];
                }
            }
            num = max(num, cnt);
        }
    }
    return num;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            ans = max(ans, cal1(i, j));
        }
    }

    cout << ans;
}