Untitled
unknown
plain_text
17 days ago
4.5 kB
3
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; 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]); } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // Check horizontal if (j + M <= n) { bool valid = true; int temp = map[i][j] + v[0]; // Khởi tạo temp for (int k = 0; k < M - 1; 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; } } if (valid) { if (isInstall) { for (int k = 0; k < M; k++) { map[i][j + k] = temp; } } cnt++; } } // Check vertical if (i + M <= n) { bool valid = true; int temp = map[i][j] + v[0]; // Khởi tạo temp for (int k = 0; k < M - 1; 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; } } if (valid) { 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++; 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; return 0; }
Leave a Comment