Untitled

mail@pastecode.io avatar
unknown
plain_text
5 months ago
6.9 kB
4
Indexable
#include<iostream>
#include<stdio.h>
#include<unordered_map>
#include<queue>
#include<bits/stdc++.h>
#define sz 80000 
using namespace std;
  
// 2-->0
//3-->1
// 4-->2
// 5-->3
  
unordered_map<int, vector<pair<int,int>>> horizontal;
unordered_map<int, vector<pair<int, int>>> vertical;
  
  
int arr[25][25];
int visited[25][25];
int g_counter = 0;
int g_n;
int max(int a, int b) {
    if (a > b)
        return a;
    return b;
}
int horizontal_p(int i, int j, int len) {
    int maxi = 0;
    int num = 0;
    if (j + len > g_n)
        return 0;
    for (int k = 0; k < len; k++) 
        maxi = max(maxi, arr[i][j+k]);
    for (int k = 0; k < len; k++) {
        int temp = maxi - arr[i][j + k]+1;
        num *= 10;
        num += temp;
    }
    return num;
}
int vertical_p(int i, int j, int len) {
    int maxi = 0;
    int num = 0;
    if (i + len > g_n)
        return 0;
    for (int k = 0; k < len; k++)
        maxi = max(maxi, arr[i+k][j]);
    for (int k = 0; k < len; k++) {
        int temp = maxi - arr[i+k][j]+1;
        num *= 10;
        num += temp;
    }
    return num;
}
  
int getReverse(int num) {
    int temp = 0;
    while (num != 0) {
        temp *= 10;
        temp += (num % 10);
        num /= 10;
    }
    return temp;
}
void init(int N, int mMap[20][20])
{
    //g_counter = 0;
    /*for (int i = 0; i < 4; i++) {
        horizontal[i].clear();
        vertical[i].clear();
    }*/
    horizontal.clear();
    vertical.clear();
    g_n = N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            arr[i][j] = mMap[i][j];
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 2; k <= 5; k++) {
                int temp_h = horizontal_p(i, j, k);
                int temp_v = vertical_p(i, j, k);
                if(temp_h!=0)
                horizontal[temp_h].push_back({i, j});
                if(temp_v!=0)
                vertical[temp_v].push_back({ i, j });
                  
            }
        }
    }
  
}
int min(int a, int b) {
    if (a < b)
        return a;
    return b;
}
int getHash(int M, int mStructure[]) {
    int mini = INT_MAX;
    int num = 0;
    for (int i = 0; i < M; i++) {
        mini = min(mini, mStructure[i]);
    }
    for (int i = 0; i < M; i++)
    {
        int temp = mStructure[i] - mini + 1;
        num *= 10;
        num += temp;
    }
    return num;
}
int numberOfCandidate(int M, int mStructure[5])
{
    int num = 0;
    int mini = INT_MAX;
    if (M == 1)
        return g_n * g_n;
    num = getHash(M, mStructure);
    int reverse_num = getReverse(num);
    int ans = 0;
    ans += horizontal[num].size();
    if(reverse_num!=num)
    ans += horizontal[reverse_num].size();
    ans += vertical[num].size();
    if(reverse_num!=num)
    ans += vertical[reverse_num].size();
    return ans;
}
int dx[4] = {-1,0,1,0 };
int dy[4] = {0,1,0,-1 };
  
int findAns(int lvl) {
    g_counter++;
    int f_ans = 0;
    queue<pair<int, int>> q;
    int i = 0, j = 0;
  
    for (int i = 0; i < g_n; i++) {
        for (int j = 0; j < g_n; j++) {
            if ((i == 0 || i == g_n - 1 || j == 0 || j == g_n - 1) && visited[i][j]!=g_counter && arr[i][j]<lvl) {
                f_ans++;
                q.push({ i,j });
                visited[i][j] = g_counter;
            }
        }
    }
    while (!q.empty()) {
        pair<int, int> temp = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                int new_x = temp.first + dx[i];
                int new_y = temp.second + dy[i];
                if (visited[new_x][new_y] != g_counter && arr[new_x][new_y] < lvl && new_x>=0 && new_x<g_n && new_y>=0 && new_y<g_n) {
                    q.push({new_x, new_y});
                    visited[new_x][new_y] = g_counter;
                    f_ans++;
                }
            }
        }
  
    }
    return f_ans;
}
int maxArea(int M, int mStructure[5], int mSeaLevel)
{
    int num = 0;
    int mini = INT_MAX;
    if (M == 1) {
        for (int i = 0; i < g_n; i++) {
            for (int j = 0; j < g_n; j++) {
                arr[i][j] += mStructure[0];
                int temp_ans = findAns(mSeaLevel);
                mini = min(mini, temp_ans);
                arr[i][j] -= mStructure[0];
            }
        }
        int sq = g_n * g_n;
        if (mini == INT_MAX)
            return -1;
        return sq - mini;
    }
      
    num = getHash(M, mStructure);
    int rev_num = 0;
    rev_num = getReverse(num);
    for (auto itr : horizontal[num]) {
        int new_x = itr.first;
        int new_y = itr.second;
        for (int i = 0; i < M; i++)
            arr[new_x][new_y + i] += mStructure[i];
        int temp_ans = findAns(mSeaLevel);
        for (int i = 0; i < M; i++)
            arr[new_x][new_y + i] -= mStructure[i];
          
      
        mini = min(mini, temp_ans);
    }
    if (rev_num != num) {
        for (auto itr : horizontal[rev_num]) {
            int new_x = itr.first;
            int new_y = itr.second;
            //int temp = num;
            for (int i = 0; i < M; i++) {
                arr[new_x][new_y + i] += mStructure[M - i - 1];
                //temp /= 10;
            }
            int temp_ans = findAns(mSeaLevel);
            //temp = num;
            for (int i = 0; i < M; i++) {
                arr[new_x][new_y + i] -= mStructure[M - i - 1];
                //temp /= 10;
            }
  
            mini = min(mini, temp_ans);
        }
    }
    if (rev_num != num) {
        for (auto itr : vertical[rev_num]) {
            int new_x = itr.first;
            int new_y = itr.second;
            //int temp = num;
            for (int i = 0; i < M; i++) {
                arr[new_x + i][new_y] += mStructure[M - i - 1];
                //temp /= 10;
            }
            int temp_ans = findAns(mSeaLevel);
            //temp = num;
            for (int i = 0; i < M; i++) {
                arr[new_x + i][new_y] -= mStructure[M - i - 1];
                //temp /= 10;
            }
  
            mini = min(mini, temp_ans);
        }
    }
    for (auto itr : vertical[num]) {
        int new_x = itr.first;
        int new_y = itr.second;
        for (int i = 0; i < M; i++)
            arr[new_x+i][new_y] += mStructure[i];
        int temp_ans = findAns(mSeaLevel);
        for (int i = 0; i < M; i++)
            arr[new_x+i][new_y] -= mStructure[i];
  
  
        mini = min(mini, temp_ans);
    }
    int sq = g_n * g_n;
    if (mini == INT_MAX)
        return -1;
    return sq - mini;
}
Leave a Comment