Untitled
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