Untitled
unknown
plain_text
17 days ago
5.0 kB
3
Indexable
Never
#include <iostream> #include <vector> #include <unordered_map> #include <string> #include <queue> using namespace std; int n, map[20][20]; bool visited[20][20]; // Đánh dấu các ô đã được kiểm tra trong BFS vector<int> v; vector<int> re_v; // Hàm khởi tạo bản đồ void init(int N, int mMap[20][20]) { for (int i = 0; i < 20; i++) { for (int j = 0; j < 20; j++) { map[i][j] = mMap[i][j]; visited[i][j] = false; } } } // Hàm kiểm tra và cập nhật bản đồ dựa trên mStructure int numberOfCandidate(int M, int mStructure[5]) { if (M == 1) return n * n; int cnt = 0; unordered_map<string, bool> horizontal_cache, vertical_cache; // Tạo các cấu trúc tăng dần và giảm dần từ mStructure for (int i = 0; i < M; i++) { v.push_back(mStructure[i]); re_v.push_back(mStructure[M - i - 1]); } // Duyệt qua các ô trên bản đồ 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++) { 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]) { // Cập nhật giá trị bản đồ tại vị trí hợp lệ for (int k = 0; k < M; k++) { map[i][j + k] = 5; // Cập nhật thành giá trị tối đa } 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++) { 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]) { // Cập nhật giá trị bản đồ tại vị trí hợp lệ for (int k = 0; k < M; k++) { map[i + k][j] = 5; // Cập nhật thành giá trị tối đa } cnt++; } } } } return cnt; } // Hàm kiểm tra tính hợp lệ của ô trong BFS bool isValid(int x, int y, int mSeaLevel) { return (x >= 0 && x < n && y >= 0 && y < n && map[x][y] >= mSeaLevel && !visited[x][y]); } // Hàm BFS để tìm và đánh dấu các đảo 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({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)) { visited[nx][ny] = true; q.push({nx, ny}); } } } } // Hàm tính số lượng đảo còn nổi sau khi nước biển dâng lên int maxArea(int M, int mStructure[5], int mSeaLevel) { // Bước 1: Cập nhật bản đồ dựa trên cấu trúc mẫu numberOfCandidate(M, mStructure); // Bước 2: Tính số lượng đảo còn nổi trên biển int island_count = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (map[i][j] >= mSeaLevel && !visited[i][j]) { BFS(i, j, mSeaLevel); island_count++; } } } return island_count; } int main() { 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] = {4, 3, 4}; cout << maxArea(3, mStructure, 3) << endl; return 0; }
Leave a Comment