[14500] 테트로미노

음... 테트리스의 모양 중에서 다른건 간단하게 생각하셨을 것 같은데...

凸이 모양이 좀 고민스러웠죠...

저는

위, 아래, 왼, 오른쪽으로 각각 가중치를 주었습니다. dfs 매개변수에서 weight라는 변수입니다.

위 = 1

아래 = 10

왼 = 100

오 = 1000

이렇게 각각 주어서

만약 세로로 세칸 짜리는 20이 될 것입니다.(0부터 시작하므로 2칸이동하면 20)

만약 가로로 세칸 짜리는 2000이 될 것입니다. 오른쪽으로 두 칸 갔기 때문입니다.

이 두가지 경우에는 추가로 2방향씩 더 검사해줍니다.

세로 방향일 경우에는 1시와 11시 대각선을 검사하고, (코드에서 (ddx[0], ddy[0]), (ddx[1], ddy[1]))

가로 방향일 경우에는 11시와 7시 방향의 대각선을 검사하면 됩니다. (코드에서 (ddx[2], ddy[2]), (ddx[3], ddy[3]))

모든 맵을 dfs하고 가장 큰 수를 출력하면 끝입니다.!

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <string.h>
#include <vector>
#include <functional>
 
#define MAX_SIZE 500
#define INF 0x7fffffff
 
using namespace std;
//input
int map[MAX_SIZE][MAX_SIZE];
int m, n;
 
//process
bool visit[MAX_SIZE][MAX_SIZE];
int max_value;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int ddx[4] = { -1, -1, -1, 1 };
int ddy[4] = { -1, 1, -1, -1 };
 
void input(){
    scanf("%d %d", &m, &n);
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            scanf("%d", &map[i][j]);
        }
    }
}
 
int pow(int n, int r){
    if (r == 0) return 1;
    else if (r % 2 == 0){
        int tmp = pow(n, r / 2);
        return tmp *tmp;
    }
    else return pow(n, r - 1) * n;
}
 
void dfs(int x, int y, int d, int sum, int weight){
    if (d == 3){
        max_value = max(max_value, sum);
        return;
    }
 
    for (int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (nx < 0 || ny < 0 || nx >= m || ny >= n || visit[nx][ny]) continue;
 
        visit[x][y] = 1;
 
        dfs(nx, ny, d + 1, sum + map[nx][ny], weight + pow(10, i));
 
        visit[x][y] = 0;
    }
 
    if (weight == 20){
        for (int i = 0; i < 2; i++){
            int nx = x + ddx[i];
            int ny = y + ddy[i];
 
            if (nx < 0 || ny < 0 || nx >= m || ny >= n || visit[nx][ny]) continue;
 
            dfs(nx, ny, d + 1, sum + map[nx][ny], weight);
        }
    }
    else if (weight == 2000){
        for (int i = 2; i < 4; i++){
            int nx = x + ddx[i];
            int ny = y + ddy[i];
 
            if (nx < 0 || ny < 0 || nx >= m || ny >= n || visit[nx][ny]) continue;
 
            dfs(nx, ny, d + 1, sum + map[nx][ny], weight);
        }
    }
 
}
 
void process(){
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            dfs(i, j, 0, map[i][j], 0);
        }
    }
    printf("%d\n", max_value);
}
 
int main(){
    input();
    process();
 
    return 0;
}