Untitled

mail@pastecode.io avatar
unknown
plain_text
15 days ago
4.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<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*n+j);

                    sum180deg = sum180deg * 10 + map[i][j+k-1] - map[i][j+k] + 5;
                    hash_hozion[sum180deg].push_back(i*n+j);
                }
                if(i + k < N) {
                    sum90deg = sum90deg * 10 + map[i+k][j] - map[i+k-1][j] + 5;
                    hash_vertical[sum90deg].push_back(j*n+i);

                    sum270deg = sum270deg * 10 + map[i+k-1][j] - map[i+k][j] + 5;
                    hash_vertical[sum270deg].push_back(j*n+i);
                }
            }
        }
    }
}

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

int bfs(int mSeaLevel) {
    // Reset mảng visit
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            visit[i][j] = 0;
        }
    }

    int cnt = n*n;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(i == 0 || i==n-1 || j==0 || j == n-1) {
                if (map[i][j] < mSeaLevel) {
                    cnt--;
                    visit[i][j] = 1;
                    q.push(make_pair(i, 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] && map[row][col] < mSeaLevel) {
                q.push(make_pair(row, col));
                cnt--;
                visit[row][col] = 1;
            }
        }
    }

    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=0; i<M-1; i++) {
        key = key * 10 + mStructure[i] - mStructure[i+1] + 5;
    }

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

            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];
            }
        }
    }

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

            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];
            }
        }
    }

    return ans;
}
Leave a Comment