Untitled
#include <iostream> #include <vector> #include <unordered_map> #include <queue> using namespace std; int n; int map[20][20], mapCp[20][20]; int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0, -1, 0}; unordered_map<int, vector<int>> hash_horizontal, hash_vertical; void init(int N, int mMap[20][20]) { n = N; hash_horizontal.clear(); hash_vertical.clear(); for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { map[i][j] = mMap[i][j]; mapCp[i][j] = mMap[i][j]; for(int k = 2; k <= 5; k++) { if(j + k > N) break; int sum0deg = 0, sum180deg = 0, sum90deg = 0, sum270deg = 0; for(int l = j + 1; l < k + j; l++) { sum0deg = sum0deg * 10 + mMap[i][l] - mMap[i][j] + 5; sum180deg = sum180deg * 10 + mMap[i][k + 2 * j - l - 1] - mMap[i][k + j - 1] + 5; sum90deg = sum90deg * 10 + mMap[l][i] - mMap[j][i] + 5; sum270deg = sum270deg * 10 + mMap[k + 2 * j - l - 1][i] - mMap[k + j - 1][i] + 5; } if(hash_horizontal.find(sum0deg) == hash_horizontal.end()) { hash_horizontal[sum0deg] = vector<int>(); } hash_horizontal[sum0deg].push_back(i * N + j); if(hash_horizontal.find(sum180deg) == hash_horizontal.end()) { hash_horizontal[sum180deg] = vector<int>(); } if(sum0deg != sum180deg) { hash_horizontal[sum180deg].push_back(i * N + j); } if(hash_vertical.find(sum90deg) == hash_vertical.end()) { hash_vertical[sum90deg] = vector<int>(); } hash_vertical[sum90deg].push_back(j * N + i); if(hash_vertical.find(sum270deg) == hash_vertical.end()) { hash_vertical[sum270deg] = vector<int>(); } if(sum90deg != sum270deg) { hash_vertical[sum270deg].push_back(j * N + i); } } } } } int numberOfCandidate(int M, int mStructure[5]) { int sum = 0, count = 0; if(M == 1) return n * n; for(int i = 1; i < M; i++) { sum = sum * 10 + mStructure[0] - mStructure[i] + 5; } if(hash_horizontal.find(sum) != hash_horizontal.end()) { count += hash_horizontal[sum].size(); } if(hash_vertical.find(sum) != hash_vertical.end()) { count += hash_vertical[sum].size(); } return count; } int bfs(int mSeaLevel) { queue<pair<int, int>> q; int cnt = 0; int visited[20][20] = {0}; for(int i = 0; i < n; i++) { if(map[0][i] < mSeaLevel) { q.push({i, 0}); visited[0][i] = 1; cnt++; } if(map[n - 1][i] < mSeaLevel) { q.push({i, n - 1}); visited[n - 1][i] = 1; cnt++; } } for(int i = 1; i < n - 1; i++) { if(map[i][0] < mSeaLevel) { q.push({0, i}); visited[i][0] = 1; cnt++; } if(map[i][n - 1] < mSeaLevel) { q.push({n - 1, i}); visited[i][n - 1] = 1; cnt++; } } while(!q.empty()) { pair<int, int> c = q.front(); q.pop(); for(int k = 0; k < 4; k++) { int x = c.first + dx[k]; int y = c.second + dy[k]; if(x >= 0 && x < n && y >= 0 && y < n && visited[y][x] == 0 && map[y][x] < mSeaLevel) { cnt++; visited[y][x] = 1; q.push({x, y}); } } } return n * n - cnt; } int check_1(int x, int y, int M, int mStructure[5]) { for(int i = 0; i < M - 1; i++) { if(map[y][x + i] + mStructure[i] != map[y][x + i + 1] + mStructure[i + 1]) return M - 1; } return 0; } int check_2(int x, int y, int M, int mStructure[5]) { for(int i = 0; i < M - 1; i++) { if(map[y + i][x] + mStructure[i] != map[y + i + 1][x] + mStructure[i + 1]) return M - 1; } return 0; } int maxArea(int M, int mStructure[5], int mSeaLevel) { int sum = 0; int mMax = -1; for(int i = 1; i < M; i++) { sum = sum * 10 + mStructure[0] - mStructure[i] + 5; } if(M == 1) { for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { map[i][j] += mStructure[0]; int countPlace = bfs(mSeaLevel); if(mMax < countPlace) { mMax = countPlace; } map[i][j] -= mStructure[0]; } } return mMax; } if(hash_horizontal.find(sum) != hash_horizontal.end()) { for(int pos : hash_horizontal[sum]) { int y = pos / n; int x = pos % n; int index = check_1(x, y, M, mStructure); int height = map[y][x] + mStructure[index]; for(int i = 0; i < M; i++) { map[y][x + i] = height; } int countPlace = bfs(mSeaLevel); if(mMax < countPlace) { mMax = countPlace; } for(int i = 0; i < M; i++) { map[y][x + i] = mapCp[y][x + i]; } } } if(hash_vertical.find(sum) != hash_vertical.end()) { for(int pos : hash_vertical[sum]) { int y = pos / n; int x = pos % n; int index = check_2(x, y, M, mStructure); int height = map[y][x] + mStructure[index]; for(int i = 0; i < M; i++) { map[y + i][x] = height; } int countPlace = bfs(mSeaLevel); if(mMax < countPlace) { mMax = countPlace; } for(int i = 0; i < M; i++) { map[y + i][x] = mapCp[y + i][x]; } } } return mMax; }
Leave a Comment