Untitled

#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;
}