Untitled
unknown
plain_text
15 days ago
3.4 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; int sum0deg = 0, sum90deg=0, sum180deg=0, sum270deg=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 k=1; k<5; k++) { if(j + k < N) { sum0deg = sum0deg * 10 + map[i][j+k] - map[i][j+k-1] + 5; if(hash_hozion.find(sum0deg) == hash_hozion.end()) { hash_hozion[sum0deg].push_back(i*n+j); } sum180deg = sum180deg * 10 + map[i][j+k-1] - map[i][j+k] + 5; if(hash_hozion.find(sum180deg) == hash_hozion.end()) { 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; if(hash_vertical.find(sum90deg) == hash_vertical.end()) { hash_vertical[sum90deg].push_back(j*n+i); } sum270deg = sum270deg * 10 + map[i+k-1][j] - map[i+k][j] +5; if(hash_vertical.find(sum270deg) == hash_vertical.end()) { 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) { //step++; 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) { 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 = temp > ans ? temp : 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 = temp > ans ? temp : ans; 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 = temp > ans ? temp : ans; for(int i=0; i<M; i++) { map[row+i][col] -= mStructure[i]; } } } return ans; }
Leave a Comment