테트로미노 14500번 [백준]

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

14500번: 테트로미노

 

백트레킹을 사용하여 풀 수 있는 문제입니다.

 

다만  ㅗ ㅓ ㅏ ㅜ 모양의 조각들은 백트레킹으로는 풀 수 없으므로 따로 함수를 만들어서 풀었습니다.

#include<bits/stdc++.h>
#include<sys/types.h>


using namespace std;
#define endl '\n'
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i, j) for(ll i=0;i<j;i++)

int n, m;
vector<vector<int>> v;

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

int range(int x, int y) {
    if (x < 0 || y < 0 || x >= n || y >= m || visited[x][y])return false;
    return true;
}

int recursive4(int x, int y, int take) {
    int ans = -1;
    if (take == 3) return v[x][y];
    rep(i, 4) {
        if (!range(x + dx[i], y + dy[i]))continue;
        visited[x][y] = true;
        ans = max(ans, recursive4(x + dx[i], y + dy[i], take + 1));
        visited[x][y] = false;
    }
    ans += v[x][y];
    return ans;
}

int notRecursive(int x, int y) {
    int ans = -1;
    if (x >= 1 && y >= 1 && x + 1 < n) {
        ans = max(ans, v[x][y] + v[x - 1][y] + v[x][y - 1] + v[x + 1][y]);
    }
    if (x >= 1 && y + 1 < m && x + 1 < n) {
        ans = max(ans, (v[x][y] + v[x - 1][y] + v[x][y + 1] + v[x + 1][y]));
    }
    if (y + 1 < m && y >= 1 && x >= 1) {
        ans = max(ans, (v[x][y] + v[x][y + 1] + v[x][y - 1] + v[x - 1][y]));
    }
    if (y + 1 < m && y >= 1 && x + 1 < n) {
        ans = max(ans, (v[x][y] + v[x][y + 1] + v[x][y - 1] + v[x + 1][y]));
    }
    return ans;
}

void solve() {
    cin >> n >> m;
    v = vector<vector<int>>(n, vector<int>(m));
    for (auto &x: v)
        for (auto &y: x)cin >> y;
    int ans = -1;

    rep(i, n) {
        rep(j, m) {
            ans = max(ans, recursive4(i, j, 0));
//            visited[i][j] = true;
            ans = max(ans, notRecursive(i, j));
        }
    }
    cout << ans << endl;
}

int main() {

    solve();
    return 0;
}