Untitled
unknown
plain_text
20 days ago
4.5 kB
2
Indexable
Never
#include <iostream> #include <vector> #include <unordered_map> #include <string> #include <queue> using namespace std; int n, map[20][20], re_map[20][20]; bool visited[20][20]; vector<int> v; vector<int> re_v; int isInstall; int temp; void init(int N, int mMap[20][20]) { isInstall = 0; n = N; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout<<mMap[i][j]<<" "; re_map[i][j] = map[i][j] = mMap[i][j]; visited[i][j] = false; } cout<<endl; } cout<<"------------------"<<endl; v.clear(); re_v.clear(); } int numberOfCandidate(int M, int mStructure[5]) { if (M == 1) return n * n; int cnt = 0; unordered_map<string, bool> horizontal_cache, vertical_cache; for (int i = 0; i < M; i++) { v.push_back(mStructure[i]); re_v.push_back(mStructure[M - i - 1]); } //Check NxN island for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // Check horizontal if (j + M <= n) { string pattern; for (int k = 0; k < M; k++) { pattern += to_string(map[i][j + k]) + ","; } if (horizontal_cache.find(pattern) == horizontal_cache.end()) { bool valid = true; for (int k = 0; k < M - 1; k++) { temp = map[i][j + k] + v[k]; if (map[i][j + k] + v[k] != map[i][j + k + 1] + v[k + 1] && map[i][j + k] + re_v[k] != map[i][j + k + 1] + re_v[k + 1]) { valid = false; break; } } horizontal_cache[pattern] = valid; } if (horizontal_cache[pattern]) { // Update value island if(isInstall) { for (int k = 0; k < M; k++) { map[i][j + k] = temp; } } cnt++; } } // Check vertical if (i + M <= n) { string pattern; for (int k = 0; k < M; k++) { pattern += to_string(map[i + k][j]) + ","; } if (vertical_cache.find(pattern) == vertical_cache.end()) { bool valid = true; for (int k = 0; k < M - 1; k++) { temp = map[i + k][j] + v[k]; if (map[i + k][j] + v[k] != map[i + k + 1][j] + v[k + 1] && map[i + k][j] + re_v[k] != map[i + k + 1][j] + re_v[k + 1]) { valid = false; break; } } vertical_cache[pattern] = valid; } if (vertical_cache[pattern]) { // Update value island if(isInstall) { for (int k = 0; k < M; k++) { map[i + k][j] = temp;; } } cnt++; } } } } return cnt; } //Check valid bool isValid(int x, int y, int mSeaLevel) { return (x >= 0 && x < n && y >= 0 && y < n && map[x][y] < mSeaLevel && !visited[x][y]); } // BFS void BFS(int x, int y, int mSeaLevel) { int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; queue<pair<int, int>> q; q.push(make_pair(x,y)); visited[x][y] = true; while (!q.empty()) { pair<int, int> current = q.front(); q.pop(); int cx = current.first; int cy = current.second; for (int i = 0; i < 4; i++) { int nx = cx + dx[i]; int ny = cy + dy[i]; if (isValid(nx, ny, mSeaLevel)) { map[nx][ny] = 0; visited[nx][ny] = true; q.push(make_pair(nx,ny)); } } } } int maxArea(int M, int mStructure[5], int mSeaLevel) { // Update map island isInstall = 1; int way_install = numberOfCandidate(M, mStructure); isInstall = 0; if(!way_install) return -1; // Count island int island_count = 0; 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) { if (map[i][j] < mSeaLevel && !visited[i][j]) { BFS(i, j, mSeaLevel); } } } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if(map[i][j] >= mSeaLevel) island_count++; /*map[i][j] = re_map[i][j]; visited[i][j] = false;*/ cout<<map[i][j]<<" "; } cout<<endl; } return island_count + 1; } int main() { //freopen("sample_input.txt", "r", stdin); cin >> n; int initial_map[20][20]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> initial_map[i][j]; } } init(n, initial_map); int mstructure[3] = {5,2,3}; cout <<maxArea(3, mstructure,6) << endl; /*int mstructure4[1] = {4}; cout<<numberofcandidate(1, mstructure4)<<endl; int mstructure2[5] = {1,5,1,3,5}; cout << maxarea(3, mstructure2, 4) << endl; int mstructure3[3] = {1,1,1}; cout <<numberofcandidate(3, mstructure3) << endl;*/ return 0; }
Leave a Comment