トロミノ


https://www.acmicpc.net/problem/14500
//
// Created by 고승빈 on 2020-10-15.
//

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int board[500][500];
    int N, M;
    cin >> N >> M;

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

    pair<int, int> shape[19][4] = {{{0, 0}, {0,  1}, {0,  2}, {0,  3}},
                                   {{0, 0}, {1,  0}, {2,  0}, {3,  0}},
                                   {{0, 0}, {0,  1}, {1,  0}, {1,  1}},
                                   {{0, 0}, {1,  0}, {2,  0}, {2,  1}},
                                   {{0, 0}, {1,  0}, {0,  1}, {0,  2}},
                                   {{0, 0}, {0,  1}, {1,  1}, {2,  1}},
                                   {{0, 0}, {0,  1}, {0,  2}, {-1, 2}},
                                   {{0, 0}, {0,  1}, {-1, 1}, {-2, 1}},
                                   {{0, 0}, {1,  0}, {1,  1}, {1,  2}},
                                   {{0, 0}, {0,  1}, {1,  0}, {2,  0}},
                                   {{0, 0}, {0,  1}, {0,  2}, {1,  2}},
                                   {{0, 0}, {1,  0}, {1,  1}, {2,  1}},
                                   {{0, 0}, {0,  1}, {-1, 1}, {-1, 2}},
                                   {{0, 0}, {-1, 0}, {-1, 1}, {-2, 1}},
                                   {{0, 0}, {0,  1}, {1,  1}, {1,  2}},
                                   {{0, 0}, {0,  1}, {1,  1}, {0,  2}},
                                   {{0, 0}, {0,  1}, {1,  1}, {-1, 1}},
                                   {{0, 0}, {0,  1}, {0,  2}, {-1, 1}},
                                   {{0, 0}, {1,  0}, {2,  0}, {1,  1}}};

    int maximum = 0;
    for (int row = 0; row < N; ++row) {
        for (int col = 0; col < M; ++col) {
            for (int sh = 0; sh < 19; ++sh) {
                int value = 0;
                bool isDone = false;
                for (int spot = 0; spot < 4; ++spot) {
                    if (!(0 <= row + shape[sh][spot].first && row + shape[sh][spot].first < N &&
                          0 <= col + shape[sh][spot].second && col + shape[sh][spot].second < M)) {
                        isDone = true;
                        break;
                    }

                    value += board[row + shape[sh][spot].first][col + shape[sh][spot].second];
                }

                if (isDone) {
                    continue;
                }

                maximum = max(maximum, value);
            }
        }
    }

    cout << maximum << endl;
    return 0;
}