Untitled

mail@pastecode.io avatar
unknown
plain_text
17 days ago
5.1 kB
2
Indexable
Never
#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int n, map[20][20], re_map[20][20];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int visit[20][20];
int step;
queue<pair<int, int>> q;
unordered_map<int, vector<pair<int, int>>> hash_hozion, hash_vertical;

void init(int N, int mMap[20][20]) {
    n = N;
    step = 0;
    hash_hozion.clear();
    hash_vertical.clear();

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            re_map[i][j] = map[i][j] = mMap[i][j];
            visit[i][j] = 0;
        }
    }

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            int sum0deg = 0, sum180deg = 0, sum90deg = 0, sum270deg = 0;
            for(int k=1; k<5; k++) {
                if(j + k < N) {
                    sum0deg = sum0deg * 10 + map[i][j+k] - map[i][j+k-1] + 5;
                    hash_hozion[sum0deg].push_back({i, j});

                    sum180deg = sum180deg + (map[i][j+k-1] - map[i][j+k] + 5) * (k == 1 ? 1 : k == 2 ? 10 : k == 3 ? 100 : 1000);
                    if(sum180deg != sum0deg) hash_hozion[sum180deg].push_back({i, j});
                }
                if(i + k < N) {
                    sum90deg = sum90deg * 10 + map[i+k][j] - map[i+k-1][j] + 5;
                    hash_vertical[sum90deg].push_back({j, i});

                    sum270deg = sum270deg + (map[i+k-1][j] - map[i+k][j] + 5) * (k == 1 ? 1 : k == 2 ? 10 : k == 3 ? 100 : 1000);
                    if(sum270deg != sum90deg) hash_vertical[sum270deg].push_back({j, i});
                }
            }
        }
    }
}

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 hash_hozion[key].size() + hash_vertical[key].size();
}

int bfs(int mSeaLevel) {
    step++;
    int cnt = n*n;
    for(int i=0; i<n; i++) {
        if(map[i][0] < mSeaLevel && visit[i][0] < step) {
            cnt--;
            visit[i][0] = step;
            q.push({i, 0});
        }
        if(map[i][n-1] < mSeaLevel && visit[i][n-1] < step) {
            cnt--;
            visit[i][n-1] = step;
            q.push({i, n-1});
        }
    }
    for(int j=1; j<n-1; j++) {
        if(map[0][j] < mSeaLevel && visit[0][j] < step) {
            cnt--;
            visit[0][j] = step;
            q.push({0, j});
        }
        if(map[n-1][j] < mSeaLevel && visit[n-1][j] < step) {
            cnt--;
            visit[n-1][j] = step;
            q.push({n-1, j});
        }
    }

    while(!q.empty()) {
        int r = q.front().first;
        int c = q.front().second;
        q.pop();

        for(int k=0; k<4; k++) {
            int row = r + dx[k];
            int col = c + dy[k];

            if(row >= 0 && row < n && col >= 0 && col < n && visit[row][col] < step && map[row][col] < mSeaLevel) {
                q.push({row, col});
                cnt--;
                visit[row][col] = step;
            }
        }
    }

    return cnt;
}

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];
                ans = max(ans, temp);
            }
        }
        return ans;
    }

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

    if(!hash_hozion[key].empty()) {
        for(auto it : hash_hozion[key]) {
            int row = it.first;
            int col = it.second;

            for(int i=0; i<M; i++) {
                map[row][col+i] += mStructure[i];
            }

            int temp = bfs(mSeaLevel);
            ans = max(ans, temp);

            for(int i=0; i<M; i++) {
                map[row][col+i] -= mStructure[i];
            }

            // Check reverse structure
            for(int i=0; i<M; i++) {
                map[row][col+i] += mStructure[M-1-i];
            }

            temp = bfs(mSeaLevel);
            ans = max(ans, temp);

            for(int i=0; i<M; i++) {
                map[row][col+i] -= mStructure[M-1-i];
            }
        }
    }

    if(!hash_vertical[key].empty()) {
        for(auto it : hash_vertical[key]) {
            int col = it.first;
            int row = it.second;

            for(int i=0; i<M; i++) {
                map[row+i][col] += mStructure[i];
            }

            int temp = bfs(mSeaLevel);
            ans = max(ans, temp);

            for(int i=0; i<M; i++) {
                map[row+i][col] -= mStructure[i];
            }

            // Check reverse structure
            for(int i=0; i<M; i++) {
                map[row+i][col] += mStructure[M-1-i];
            }

            temp = bfs(mSeaLevel);
            ans = max(ans, temp);

            for(int i=0; i<M; i++) {
                map[row+i][col] -= mStructure[M-1-i];
            }
        }
    }

    return ans;
}
Leave a Comment