14500 중첩이용 풀이

#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

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

int map[500][500];
bool visit[500][500];

int startx, starty;
int customernum = 0;
int ret= 0;

void bfs(int x, int y, int cnt, int sum) {
    if (cnt == 3) {
        if (ret < sum) 
            ret = sum;
        return;
    }

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= n || ny >= m || nx < 0 || ny < 0) continue;
        if (visit[nx][ny] == 1) continue;
        visit[nx][ny] = true;
        bfs(nx, ny, cnt + 1, sum + map[nx][ny]);
        visit[nx][ny] = false;
    }

    return;
}

void fuckshape(int y, int x) {

    // ㅜ
    if (y + 1 < n && x + 2 < m)
        ret = max(ret, map[y][x] + map[y][x + 1] + map[y][x + 2] + map[y + 1][x + 1]);
    // ㅏ
    if (y + 2 < n && x + 1 < m)
        ret = max(ret, map[y][x] + map[y + 1][x] + map[y + 1][x + 1] + map[y + 2][x]);
    // ㅗ
    if (y - 1 >= 0 && x + 2 < m)
        ret = max(ret, map[y][x] + map[y][x + 1] + map[y][x + 2] + map[y - 1][x + 1]);
    // ㅓ
    if (y + 2 < n && x - 1 >= 0)
        ret = max(ret, map[y][x] + map[y + 1][x] + map[y + 1][x - 1] + map[y + 2][x]);

    return;
}

int main() {
    cin >> n >> m;
    vector<int> v;
    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++) {
            visit[i][j] = true;
            bfs(i, j, 0, map[i][j]);
            visit[i][j] = false;

            fuckshape(i, j);
        }
    }

    cout << ret;
    return 0;
}

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