# Untitled

unknown
plain_text
14 days ago
5.2 kB
3
Indexable
Never
```#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

// FIXME: Consider using const for these values
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();

// FIXME: Clear the queue
while(!q.empty()) q.pop();

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 * 10 + map[i][j+k-1] - map[i][j+k] + 5;
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({i, j});

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

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 row = it.first;
int col = 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;
}

// FIXME: Consider adding a reset() function to clear all global state between test cases```