BOJ. Tetromino (14500)

[Link] https://www.acmicpc.net/problem/14500 · 한국어 · 日本語

The board is an `N × M` grid, and a tetromino covers four cells connected by shared sides. We need the maximum sum covered by any placement, including all rotations and reflections of the five tetromino types.

A depth-first search that extends a simple path by one adjacent cell finds the straight, L, S, and Z forms, but it cannot form a T: in a T, the three neighbors of the junction include a branch, rather than a single four-cell path. We therefore search every simple path of length four and separately check the four T orientations centered at each cell. Boundary checks are made before reading each cell, so thin boards and placements on edges are handled naturally.

Each cell is used as a search start a constant number of times. The depth-four search has a constant branching factor, and checking four T orientations also takes constant work, so the total time is O(NM) with a constant shape factor. The board values are read as long long and accumulated in long long, avoiding overflow in the sum.

{% raw %}

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int n, m;
vector<vector<long long>> board;
vector<vector<bool>> visited;
long long answer = 0;

const int dr[4] = {-1, 1, 0, 0};
const int dc[4] = {0, 0, -1, 1};

void dfs(int r, int c, int count, long long sum) {
    if (count == 4) {
        answer = max(answer, sum);
        return;
    }

    for (int d = 0; d < 4; ++d) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (nr < 0 || nr >= n || nc < 0 || nc >= m || visited[nr][nc]) continue;

        visited[nr][nc] = true;
        dfs(nr, nc, count + 1, sum + board[nr][nc]);
        visited[nr][nc] = false;
    }
}

void checkT(int r, int c) {
    const int shapes[4][3][2] = {
        {{0, -1}, {0, 1}, {-1, 0}},
        {{0, -1}, {0, 1}, {1, 0}},
        {{-1, 0}, {1, 0}, {0, -1}},
        {{-1, 0}, {1, 0}, {0, 1}}
    };

    for (const auto& shape : shapes) {
        long long sum = board[r][c];
        bool valid = true;
        for (const auto& offset : shape) {
            int nr = r + offset[0];
            int nc = c + offset[1];
            if (nr < 0 || nr >= n || nc < 0 || nc >= m) {
                valid = false;
                break;
            }
            sum += board[nr][nc];
        }
        if (valid) answer = max(answer, sum);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    board.assign(n, vector<long long>(m));
    visited.assign(n, vector<bool>(m, false));
    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < m; ++c) cin >> board[r][c];
    }

    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < m; ++c) {
            visited[r][c] = true;
            dfs(r, c, 1, board[r][c]);
            visited[r][c] = false;
            checkT(r, c);
        }
    }

    cout << answer << '\n';
    return 0;
}

{% endraw %}