14500번: 테트로미노

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

풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>

using namespace std;
int N, M;
int board[501][501];
int check[501][501];
int maxi = -2147000000;

int dirI[4] = {-1, 0, 1, 0};
int dirJ[4] = {0, 1, 0, -1};

int shapeI[4][3] = {
    {0, -1, 0},
    {0, 1, 0},
    {1, 0, -1},
    {-1, 0, 1},
};
int shapeJ[4][3] = {
    {-1, 0, 1},
    {1, 0, -1},
    {0, -1, 0},
    {0, 1, 0},
};

void CheckShape(int i, int j, int sum)
{
    int originSum = sum;

    for (int k = 0; k < 4; ++k)
    {
        sum = originSum;

        for (int l = 0; l < 3; ++l)
        {
            int checkI = i + shapeI[k][l];
            int checkJ = j + shapeJ[k][l];

            if (checkI < 0 || checkJ < 0 || checkI >= N || checkJ >= M)
                break;

            sum += board[checkI][checkJ];
        }

        if (sum > maxi)
        {
            maxi = sum;
        }
    }
}

void DFS(int L, int i, int j, int sum)
{
    if (L == 4)
    {
        if (sum > maxi)
        {
            maxi = sum;
        }
    }
    else
    {
        check[i][j] = 1;

        for (int k = 0; k < 4; ++k)
        {
            int checkI = i + dirI[k];
            int checkJ = j + dirJ[k];

            if (checkI < 0 || checkJ < 0 || checkI >= N || checkJ >= M)
                continue;

            if (check[checkI][checkJ] == 1)
                continue;

            check[checkI][checkJ] = 1;
            DFS(L + 1, checkI, checkJ, sum + board[checkI][checkJ]);
            check[checkI][checkJ] = 0;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("input.txt", "rt", stdin);

    cin >> N >> M;

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            cin >> board[i][j];
        }
    }

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            DFS(1, i, j, board[i][j]);

            check[i][j] = 0;

            CheckShape(i, j, board[i][j]);
        }
    }

    cout << maxi;

    return 0;
}

풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>

using namespace std;
int N, M;
int board[501][501];
int check[501][501];
int maxi = -2147000000;

int dirI[4] = {-1, 0, 1, 0};
int dirJ[4] = {0, 1, 0, -1};

int shapeI1[3] = {0, -1, 0};
int shapeJ1[3] = {-1, 0, 1};

int shapeI2[3] = {0, 1, 0};
int shapeJ2[3] = {-1, 0, 1};

int shapeI3[3] = {1, 0, -1};
int shapeJ3[3] = {0, -1, 0};

int shapeI4[3] = {-1, 0, 1};
int shapeJ4[3] = {0, 1, 0};

void CheckShape1(int i, int j, int sum)
{
    for (int k = 0; k < 3; ++k)
    {
        int checkI = i + shapeI1[k];
        int checkJ = j + shapeJ1[k];

        if (checkI < 0 || checkJ < 0 || checkI >= N || checkJ >= M)
            return;

        sum += board[checkI][checkJ];
    }

    if (sum > maxi)
    {
        maxi = sum;
    }
}

void CheckShape2(int i, int j, int sum)
{
    for (int k = 0; k < 3; ++k)
    {
        int checkI = i + shapeI2[k];
        int checkJ = j + shapeJ2[k];

        if (checkI < 0 || checkJ < 0 || checkI >= N || checkJ >= M)
            return;

        sum += board[checkI][checkJ];
    }

    if (sum > maxi)
    {
        maxi = sum;
    }
}

void CheckShape3(int i, int j, int sum)
{
    for (int k = 0; k < 3; ++k)
    {
        int checkI = i + shapeI3[k];
        int checkJ = j + shapeJ3[k];

        if (checkI < 0 || checkJ < 0 || checkI >= N || checkJ >= M)
            return;

        sum += board[checkI][checkJ];
    }

    if (sum > maxi)
    {
        maxi = sum;
    }
}

void CheckShape4(int i, int j, int sum)
{
    for (int k = 0; k < 3; ++k)
    {
        int checkI = i + shapeI4[k];
        int checkJ = j + shapeJ4[k];

        if (checkI < 0 || checkJ < 0 || checkI >= N || checkJ >= M)
            return;

        sum += board[checkI][checkJ];
    }

    if (sum > maxi)
    {
        maxi = sum;
    }
}

void DFS(int L, int i, int j, int sum)
{
    if (L == 4)
    {
        if (sum > maxi)
        {
            maxi = sum;
        }
    }
    else
    {
        check[i][j] = 1;

        for (int k = 0; k < 4; ++k)
        {
            int checkI = i + dirI[k];
            int checkJ = j + dirJ[k];

            if (checkI < 0 || checkJ < 0 || checkI >= N || checkJ >= M)
                continue;

            if (check[checkI][checkJ] == 1)
                continue;

            check[checkI][checkJ] = 1;
            DFS(L + 1, checkI, checkJ, sum + board[checkI][checkJ]);
            check[checkI][checkJ] = 0;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("input.txt", "rt", stdin);

    cin >> N >> M;

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            cin >> board[i][j];
        }
    }

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            DFS(1, i, j, board[i][j]);

            check[i][j] = 0;

            CheckShape1(i, j, board[i][j]);
            CheckShape2(i, j, board[i][j]);
            CheckShape3(i, j, board[i][j]);
            CheckShape4(i, j, board[i][j]);
        }
    }

    cout << maxi;

    return 0;
}