Untitled

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