boj 14500 테트로미노

www.acmicpc.net/problem/14500

14500번: 테트로미노

크기가 N * M인 종이에 위와 같은 테트로미노를 하나 놓습니다.

그리고 이 테트로미노는 회전, 대칭한 모양이 가능합니다.

 

한개를 놓으면 되기때문에 각 칸에서의 모든 경우를 다 체크해야합니다.

테트로미노 중 'ㅏ', 'ㅓ', 'ㅗ', 'ㅜ' 모양을 제외하면 한붓 그리기가 가능하므로 dfs로 구할 수 있습니다.

dfs로 가능한 모양들은 dfs를 돌려줘서 4칸을 방문할 때마다 ans를 갱신해줍니다.

 

 

 

그 다음 한붓그리기가 안되는 모양인 'ㅏ', 'ㅓ', 'ㅗ', 'ㅜ' 모양에 대한 처리를 합니다.

저는 이 모양들을 좌표로 이용하였습니다.

 

 

위와 같은 그림처럼 좌표값을 하나하나 비교하였고 각 모양마다 올 수 있는 최소, 최대 좌표값의 범위를 체크하고, 

각각 합의 최댓값을 갱신해주었습니다.

 

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int list[501][501];
bool visit[501][501];
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int N, M, ans;
 
void dfs(int x, int y, int cnt, int sum) {
    if (cnt == 4) {
        ans = max(ans, sum);
        return;
    }
 
    for (int i = 0; i < 4; i++) {
        int nx = x + direct[i][0];
        int ny = y + direct[i][1];
 
        if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
        if (visit[nx][ny]) continue;
 
        visit[nx][ny] = true;
        dfs(nx, ny, cnt + 1, sum + list[nx][ny]);
        visit[nx][ny] = false;
    }
}
 
void func() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            visit[i][j] = true;
            dfs(i, j, 1, list[i][j]);
            visit[i][j] = false;
 
            if (i + 2 < N && j + 1 < M) {
                ans = max(ans, list[i][j] + list[i + 1][j] + list[i + 2][j] + list[i + 1][j + 1]);
            }
            if (i + 1 < N && j - 1 >= 0 && j + 1 < M) {
                ans = max(ans, list[i][j] + list[i + 1][j - 1] + list[i + 1][j] + list[i + 1][j + 1]);
            }
            if (i + 1 < N && j + 2 < M) {
                ans = max(ans, list[i][j] + list[i][j + 1] + list[i][j + 2] + list[i + 1][j + 1]);
            }
            if (i - 1 >= 0 && i + 1 < N && j + 1 < M) {
                ans = max(ans, list[i][j] + list[i - 1][j + 1] + list[i][j + 1] + list[i + 1][j + 1]);
            }
        }
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> list[i][j];
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}