백준[14500] 테트로미노

문제 설명

문제 링크

http://icpc.me/14500

풀이

ㅜ모양을 제외한 나머지 모양은 잘 관찰해보면, 어떤 점 하나를 시작으로 어떻게 가든 한번 갔던 칸으로 돌아가지 않으면서 상하좌우로 4칸을 가는 모든 경우를 나타낸다. 그렇기 때문에 백트래킹을 하며 4칸을 고르면 된다.

ㅜ는 예외처리를 하여, 90도씩 돌리는 경우를 4개 고려해주면 된다.

코드

#include <cstdio>
#include <algorithm>

using namespace std;

const int NN = 502;

int arr[NN][NN], ans, n, m;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool visited[NN][NN];

void solve(int y, int x, int sum, int sz) {
    if (sz == 4) {
        ans = max(ans, sum);
        return;
    }
    for (int i = 0; i < 4; i++) {
        int ny = y + dir[i][0], nx = x + dir[i][1];
        if (ny >= n || nx >= m || ny < 0 || nx < 0) continue;
        if (!visited[ny][nx]) {
            visited[ny][nx] = true;
            solve(ny, nx, sum + arr[ny][nx], sz + 1);
            visited[ny][nx] = false;
        }
    }
}


void u(int y, int x) {
    if (x + 2 < m && y - 1 >= 0) {
        int sum = arr[y][x] + arr[y][x + 1] + arr[y][x + 2] + arr[y - 1][x + 1];
        ans = max(sum, ans);
    }
    if (x + 2 < m && y + 1 < n) {
        int sum = arr[y][x] + arr[y][x + 1] + arr[y][x + 2] + arr[y + 1][x + 1];
        ans = max(sum, ans);
    } 
    if (y + 2 < n && x - 1 >= 0) {
        int sum = arr[y][x] + arr[y + 1][x] + arr[y + 2][x] + arr[y + 1][x - 1];
        ans = max(sum, ans);
    } 
    if (y + 2 < n && x + 1 < m) {
        int sum = arr[y][x] + arr[y + 1][x] + arr[y + 2][x] + arr[y + 1][x + 1];
        ans = max(sum, ans);
    } 
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) scanf("%d", &arr[i][j]);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            visited[i][j] = true;
            solve(i, j, arr[i][j], 1);
            visited[i][j] = false;
            u(i, j);
        }
    }
    printf("%d", ans);
}