Untitled

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

int n;
int map[20][20], mapCp[20][20];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
unordered_map<int, vector<int>> hash_horizontal, hash_vertical;

void init(int N, int mMap[20][20]) {
    n = N;
    hash_horizontal.clear();
    hash_vertical.clear();
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            map[i][j] = mMap[i][j];
            mapCp[i][j] = mMap[i][j];
            for(int k = 2; k <= 5; k++) {
                if(j + k > N) break;
                int sum0deg = 0, sum180deg = 0, sum90deg = 0, sum270deg = 0;
                for(int l = j + 1; l < k + j; l++) {
                    sum0deg = sum0deg * 10 + mMap[i][l] - mMap[i][j] + 5;
                    sum180deg = sum180deg * 10 + mMap[i][k + 2 * j - l - 1] - mMap[i][k + j - 1] + 5;
                    sum90deg = sum90deg * 10 + mMap[l][i] - mMap[j][i] + 5;
                    sum270deg = sum270deg * 10 + mMap[k + 2 * j - l - 1][i] - mMap[k + j - 1][i] + 5;
                }
                if(hash_horizontal.find(sum0deg) == hash_horizontal.end()) {
                    hash_horizontal[sum0deg] = vector<int>();
                }
                hash_horizontal[sum0deg].push_back(i * N + j);

                if(hash_horizontal.find(sum180deg) == hash_horizontal.end()) {
                    hash_horizontal[sum180deg] = vector<int>();
                }
                if(sum0deg != sum180deg) {
                    hash_horizontal[sum180deg].push_back(i * N + j);
                }

                if(hash_vertical.find(sum90deg) == hash_vertical.end()) {
                    hash_vertical[sum90deg] = vector<int>();
                }
                hash_vertical[sum90deg].push_back(j * N + i);
                if(hash_vertical.find(sum270deg) == hash_vertical.end()) {
                    hash_vertical[sum270deg] = vector<int>();
                }
                if(sum90deg != sum270deg) {
                    hash_vertical[sum270deg].push_back(j * N + i);
                }
            }
        }
    }
}

int numberOfCandidate(int M, int mStructure[5]) {
    int sum = 0, count = 0;
    if(M == 1) return n * n;
    for(int i = 1; i < M; i++) {
        sum = sum * 10 + mStructure[0] - mStructure[i] + 5;
    }
    if(hash_horizontal.find(sum) != hash_horizontal.end()) {
        count += hash_horizontal[sum].size();
    }
    if(hash_vertical.find(sum) != hash_vertical.end()) {
        count += hash_vertical[sum].size();
    }
    return count;
}

int bfs(int mSeaLevel) {
    queue<pair<int, int>> q;
    int cnt = 0;
    int visited[20][20] = {0};
    for(int i = 0; i < n; i++) {
        if(map[0][i] < mSeaLevel) {
            q.push({i, 0});
            visited[0][i] = 1;
            cnt++;
        }
        if(map[n - 1][i] < mSeaLevel) {
            q.push({i, n - 1});
            visited[n - 1][i] = 1;
            cnt++;
        }
    }
    for(int i = 1; i < n - 1; i++) {
        if(map[i][0] < mSeaLevel) {
            q.push({0, i});
            visited[i][0] = 1;
            cnt++;
        }
        if(map[i][n - 1] < mSeaLevel) {
            q.push({n - 1, i});
            visited[i][n - 1] = 1;
            cnt++;
        }
    }
    while(!q.empty()) {
        pair<int, int> c = q.front();
        q.pop();
        for(int k = 0; k < 4; k++) {
            int x = c.first + dx[k];
            int y = c.second + dy[k];
            if(x >= 0 && x < n && y >= 0 && y < n && visited[y][x] == 0 && map[y][x] < mSeaLevel) {
                cnt++;
                visited[y][x] = 1;
                q.push({x, y});
            }
        }
    }
    return n * n - cnt;
}

int check_1(int x, int y, int M, int mStructure[5]) {
    for(int i = 0; i < M - 1; i++) {
        if(map[y][x + i] + mStructure[i] != map[y][x + i + 1] + mStructure[i + 1]) return M - 1;
    }
    return 0;
}

int check_2(int x, int y, int M, int mStructure[5]) {
    for(int i = 0; i < M - 1; i++) {
        if(map[y + i][x] + mStructure[i] != map[y + i + 1][x] + mStructure[i + 1]) return M - 1;
    }
    return 0;
}

int maxArea(int M, int mStructure[5], int mSeaLevel) {
    int sum = 0;
    int mMax = -1;
    for(int i = 1; i < M; i++) {
        sum = sum * 10 + mStructure[0] - mStructure[i] + 5;
    }
    if(M == 1) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                map[i][j] += mStructure[0];
                int countPlace = bfs(mSeaLevel);
                if(mMax < countPlace) {
                    mMax = countPlace;
                }
                map[i][j] -= mStructure[0];
            }
        }
        return mMax;
    }
    if(hash_horizontal.find(sum) != hash_horizontal.end()) {
        for(int pos : hash_horizontal[sum]) {
            int y = pos / n; int x = pos % n;
            int index = check_1(x, y, M, mStructure);
            int height = map[y][x] + mStructure[index];
            for(int i = 0; i < M; i++) {
                map[y][x + i] = height;
            }
            int countPlace = bfs(mSeaLevel);
            if(mMax < countPlace) {
                mMax = countPlace;
            }
            for(int i = 0; i < M; i++) {
                map[y][x + i] = mapCp[y][x + i];
            }
        }
    }
    if(hash_vertical.find(sum) != hash_vertical.end()) {
        for(int pos : hash_vertical[sum]) {
            int y = pos / n; int x = pos % n;
            int index = check_2(x, y, M, mStructure);
            int height = map[y][x] + mStructure[index];
            for(int i = 0; i < M; i++) {
                map[y + i][x] = height;
            }
            int countPlace = bfs(mSeaLevel);
            if(mMax < countPlace) {
                mMax = countPlace;
            }
            for(int i = 0; i < M; i++) {
                map[y + i][x] = mapCp[y + i][x];
            }
        }
    }
    return mMax;
}