Untitled

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;

int n, map[21][21];
int visit[21][21];
int stepvisit = 0;

struct Structure {
    int r, c;
    bool reverse;
};

vector<Structure> structures;
unordered_map<int, vector<int>> horizontal_structures;
unordered_map<int, vector<int>> vertical_structures;

int coso[5] = { 0, 1, 10, 100, 1000 };
int dir[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

void add_structure(int r, int c, int value, bool rev, bool is_horizontal) {
    structures.push_back({ r, c, rev });
    int idx = structures.size() - 1;
    if (is_horizontal) {
        horizontal_structures[value].push_back(idx);
    }
    else {
        vertical_structures[value].push_back(idx);
    }
}

void init(int N, int mMap[20][20]) {
    n = N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            map[i][j] = mMap[i][j];
            visit[i][j] = 0;
        }
    }

    structures.clear();
    horizontal_structures.clear();
    vertical_structures.clear();

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int ngang[2] = { 0, 0 }, doc[2] = { 0, 0 };
            for (int k = 1; k < 5; k++) {
                if (j + k < N) {
                    ngang[0] = ngang[0] * 10 + (map[i][j + k] - map[i][j + k - 1] + 5);
                    add_structure(i, j, ngang[0], false, true);

                    ngang[1] = ngang[1] + (map[i][j + k - 1] - map[i][j + k] + 5) * coso[k];
                    if (ngang[1] != ngang[0]) {
                        add_structure(i, j, ngang[1], true, true);
                    }
                }
                if (i + k < N) {
                    doc[0] = doc[0] * 10 + (map[i + k][j] - map[i + k - 1][j] + 5);
                    add_structure(i, j, doc[0], false, false);

                    doc[1] = doc[1] + (map[i + k - 1][j] - map[i + k][j] + 5) * coso[k];
                    if (doc[1] != doc[0]) {
                        add_structure(i, j, doc[1], true, false);
                    }
                }
            }
        }
    }
}

int numberOfCandidate(int M, int mStructure[5]) {
    if (M == 1) return n * n;
    int key = 0;
    for (int i = 1; i < M; i++) {
        key = key * 10 + (mStructure[i - 1] - mStructure[i] + 5);
    }
    return horizontal_structures[key].size() + vertical_structures[key].size();
}

int bfs(int mSealevel) {
    stepvisit++;
    int counter = n * n;
    queue<pair<int, int>> q;

    // Check edges
    for (int i = 0; i < n; i++) {
        if (map[i][0] < mSealevel && visit[i][0] < stepvisit) {
            counter--;
            visit[i][0] = stepvisit;
            q.push({ i, 0 });
        }
        if (map[i][n - 1] < mSealevel && visit[i][n - 1] < stepvisit) {
            counter--;
            visit[i][n - 1] = stepvisit;
            q.push({ i, n - 1 });
        }
        if (map[0][i] < mSealevel && visit[0][i] < stepvisit) {
            counter--;
            visit[0][i] = stepvisit;
            q.push({ 0, i });
        }
        if (map[n - 1][i] < mSealevel && visit[n - 1][i] < stepvisit) {
            counter--;
            visit[n - 1][i] = stepvisit;
            q.push({ n - 1, i });
        }
    }

    while (!q.empty()) {
        int r = q.front().first;
        int c = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int row = r + dir[i][0];
            int col = c + dir[i][1];
            if (row >= 0 && row < n && col >= 0 && col < n &&
                visit[row][col] < stepvisit && map[row][col] < mSealevel) {
                q.push({ row, col });
                counter--;
                visit[row][col] = stepvisit;
            }
        }
    }
    return counter;
}

int maxArea(int M, int mStructure[5], int mSeaLevel) {
    int ans = -1;
    if (M == 1) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] += mStructure[0];
                int temp = bfs(mSeaLevel);
                map[i][j] -= mStructure[0];
                if (temp > ans) ans = temp;
            }
        }
        return ans;
    }

    int key = 0;
    for (int i = 1; i < M; i++) {
        key = key * 10 + (mStructure[i - 1] - mStructure[i] + 5);
    }

    for (int is_horizontal = 0; is_horizontal <= 1; is_horizontal++) {
        auto& structures_map = is_horizontal ? horizontal_structures : vertical_structures;
        if (structures_map.find(key) == structures_map.end()) continue;

        for (int idx : structures_map[key]) {
            Structure& s = structures[idx];
            for (int i = 0; i < M; i++) {
                int value = s.reverse ? mStructure[M - 1 - i] : mStructure[i];
                if (is_horizontal) {
                    map[s.r][s.c + i] += value;
                }
                else {
                    map[s.r + i][s.c] += value;
                }
            }
            int temp = bfs(mSeaLevel);
            if (temp > ans) ans = temp;
            for (int i = 0; i < M; i++) {
                int value = s.reverse ? mStructure[M - 1 - i] : mStructure[i];
                if (is_horizontal) {
                    map[s.r][s.c + i] -= value;
                }
                else {
                    map[s.r + i][s.c] -= value;
                }
            }
        }
    }
    return ans;
}

int main() {
    int N, mMap[20][20];
    cin >> N;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> mMap[i][j];

    init(N, mMap);

    int M1 = 5, mStructure1[5] = { 1, 5, 1, 3, 5 };
    cout << maxArea(M1, mStructure1, 4) << endl;

    int M3 = 3, mStructure3[3] = { 1,1,1 };
    cout << numberOfCandidate(M3, mStructure3) << endl;

    int M2 = 3, mStructure2[3] = { 5, 2, 3 };
    cout << maxArea(M2, mStructure2, 6) << endl;

    return 0;
}