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

문제

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

정사각형은 서로 겹치면 안 된다.
도형은 모두 연결되어 있어야 한다.
정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

입력

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

풀이

코드

#include <iostream>
#define max_int 501
using namespace  std;

int n, m, a[max_int][max_int], result;
bool check[max_int][max_int];

int dx[] = {0, 0, 1, -1};
int dy[] = {-1, 1, 0, 0};

int ex[4][4] = {{0, 0, 0, 1}, {0, 1, 2, 1}, {0, 0, 0, -1}, {0, -1, 0, 1}};
int ey[4][4] = {{0, 1, 2, 1}, {0, 0, 0, 1}, {0, 1, 2, 1}, {0, 1, 1, 1}};


int max(int a, int b){
    return a > b ? a : b;
}

void dfs(int x, int y, int sum_value, int length){
    if(length >= 4){
        result = max(result, sum_value);
        return;
    }

    for(int i=0; i<4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(nx < 1 || nx > n || ny < 1 || ny > m) continue;

        if(!check[nx][ny]) {
            check[nx][ny] = true;

            dfs(nx, ny, sum_value + a[nx][ny], length + 1);
            check[nx][ny] = false;
        }
    }
}


void check_exshape(int x, int y){
    for(int i=0; i<4; i++){

        bool isOut = false;
        int sum_value = 0;

        for(int j=0; j<4; j++){
            int nx = x + ex[i][j];
            int ny = y + ey[i][j];

            if(nx < 1 || nx > n || ny < 1 || ny > m) {
                isOut = true;
                break;
            }
            else {
                sum_value += a[nx][ny];
            }
        }
        if(!isOut) {
            result = max(result, sum_value);
        }
    }
 
 
int main(){

    // 입력
    scanf("%d %d", &n, &m);

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            scanf("%d", &a[i][j]);
        }
    }


    // 2. 2차원 배열 각각의 원소에서 검사를 수행합니다.
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            // 1) DFS 로 검사

            // 방문했던 점을 또 방문해야하기 때문에
            // 들어가기전 체크를 해주고, 끝났을때 체크를 해제해줍니다.
            check[i][j] = true;
            dfs(i, j, a[i][j], 1);

            // 체크를 해제하면 무한루프에 들어가 않을까 걱정할 수 있습니다.
            // 길이로 재귀를 중단시키기 때문에, 수행횟수는 4 * 3 * 3, 한점에서 최대 36번 수행됩니다.
            check[i][j] = false;

            // 2) ㅏ 모양 검사
            check_exshape(i, j);
        }
    }


    // 3. 출력
    printf("%d\n", result);
}