[BOJ] 14500 테트로미노(브루트포스, 복습).cpp

#include <iostream>
using namespace std;

int map[500][500];
bool check[500][500];
int n, m;
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
int ans = 0;

void go(int x, int y, int sum, int cnt) {
    if (cnt == 4) {
        if (ans < sum) ans = sum;
        return;
    }
    if (x < 0 || x >= n || y < 0 || y >= m) return;
    if (check[x][y]) return;

    check[x][y] = true;
    for (int k = 0; k < 4; k++) {
        go(x+dx[k], y+dy[k], sum+map[x][y], cnt+1);
    }
    check[x][y] = false;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            go(i, j, 0, 0);

            if (j+2 < m) {
                int temp = map[i][j] + map[i][j+1] + map[i][j+2];
                // ㅗ 모양 체크
                if (i-1 >= 0) {
                    int temp2 = temp + map[i-1][j+1];
                    if (ans < temp2) ans = temp2;
                }
                // ㅜ 모양 체크
                if (i+1 < n) {
                    int temp2 = temp + map[i+1][j+1];
                    if (ans < temp2) ans = temp2;
                }
            }
            if (i+2 < n) {
                int temp = map[i][j] + map[i+1][j] + map[i+2][j];
                // ㅏ 모양 체크
                if (j+1 < n) {
                    int temp2 = temp + map[i+1][j+1];
                    if (ans < temp2) ans = temp2;
                }
                // ㅓ 모양 체크
                if (j-1 >= 0) {
                    int temp2 = temp + map[i+1][j-1];
                    if (ans < temp2) ans = temp2;
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}