Untitled
unknown
plain_text
20 days ago
6.9 kB
4
Indexable
Never
#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