[C++] 백준 14500번 테트로미노 (삼성 SW 역량 테스트 기출 문제)

#include <iostream>
#include <string.h>

using namespace std;

int offset_r[4] = {0, 1, 0, -1};
int offset_c[4] = {1, 0, -1, 0};

int Max(int a, int b) {
    return a > b ? a : b;
}

int result;

int WithinRange(int r, int c, int N, int M) {
    if (r < N && c < M && r >= 0 && c >= 0) return 1;
    else return 0;
}

void Solve(int *graph, int *visit, int r, int c, int N, int M, int cnt, int _sum) {
    visit[r * M + c] = 1;
    
    if(cnt + 1 == 4) {
        result = Max(result, _sum + graph[r * M + c]);
        visit[r * M + c] = 0;
        return;
    }
    
    for (int i = 0; i < 4; i++) {
        if(WithinRange(r + offset_r[i], c + offset_c[i], N, M)) {
            if(visit[(r + offset_r[i]) * M + (c + offset_c[i])] == 0) {
                Solve(graph, visit, r+offset_r[i], c+offset_c[i], N, M, cnt+1, _sum + graph[r * M + c]);
            }
        }
    }
    visit[r * M + c] = 0;
    
}
int main()
{
    int N, M;
    cin >> N >> M;
    int *graph = new int[N * M];
    int *visit = new int[N * M];
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> graph[i * M + j];
        }
    }
    
    
    int temp = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            for (int k = 0; k < 4; k++) {
                temp = graph[i * M + j];

                for (int l = 0; l < 4; l++) {
                    if (l!=k) {
                        if(!WithinRange((i+offset_r[l]), (j + offset_c[l]), N, M)) {
                            break;
                        } else {
                            temp += graph[(i+offset_r[l]) * M + (j + offset_c[l])];
                        }
                    }
                }
                result = Max(result, temp);
            }
            // memset(visit, 0, sizeof(int) * N * M);
            Solve(graph, visit, i, j, N, M, 0, 0);
        }
    }
    
    cout << result;
    delete[] graph;
    delete[] visit;
    return 0;
}