Untitled

#include <iostream>
#define MAX_N 100

using namespace std;

int N;
int matrix[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];

const int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

void initVisited() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            visited[i][j] = false;
        }
    }
}

bool isValid(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < N;
}

int dfs(int x, int y, int value) {
    visited[x][y] = true;
    int size = 1;

    for (int i = 0; i < 4; i++) {
        int nx = x + directions[i][0];
        int ny = y + directions[i][1];

        if (isValid(nx, ny) && !visited[nx][ny] && matrix[nx][ny] == value) {
            size += dfs(nx, ny, value);
        }
    }

    return size;
}

void findLargestRegion(int x, int y, int &maxValue, int &maxSize) {
    initVisited();
    maxValue = 0;
    maxSize = 0;
    bool localVisited[MAX_N][MAX_N] = {false};

    for (int i = 0; i < 4; i++) {
        int nx = x + directions[i][0];
        int ny = y + directions[i][1];

        if (isValid(nx, ny) && matrix[nx][ny] != 0 && !localVisited[nx][ny]) {
            initVisited();
            int size = dfs(nx, ny, matrix[nx][ny]);
            localVisited[nx][ny] = true;
            if (size > maxSize || (size == maxSize && matrix[nx][ny] > maxValue)) {
                maxSize = size;
                maxValue = matrix[nx][ny];
            }
        }
    }
}

void mergeZeros() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (matrix[i][j] == 0) {
                int maxValue, maxSize;
                findLargestRegion(i, j, maxValue, maxSize);
                if (maxValue > 0) {
                    matrix[i][j] = maxValue;
                }
            }
        }
    }
}

int countRegions() {
    initVisited();
    int regions = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (!visited[i][j]) {
                dfs(i, j, matrix[i][j]);
                regions++;
            }
        }
    }

    return regions;
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> matrix[i][j];
        }
    }

    mergeZeros();
    int regions = countRegions();
    cout << regions << endl;

    return 0;
}