Untitled

#include <iostream>

using namespace std;

const int MAX_N = 100;
int map[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
int n;

// Hướng di chuyển: trên, dưới, trái, phải
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

// Kiểm tra vị trí có hợp lệ trong bản đồ không
bool isValid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n;
}

// BFS để thay thế các booth 0 thành booth có tần suất lớn nhất xung quanh
void replaceZeros(int startX, int startY) {
    // Khởi tạo hàng đợi thủ công
    int queueX[MAX_N * MAX_N], queueY[MAX_N * MAX_N];
    int front = 0, rear = 0;

    // Mảng tần suất các booth 1-5
    int freq[6] = {0};

    // Mảng lưu các tọa độ của các booth 0
    int zerosX[MAX_N * MAX_N], zerosY[MAX_N * MAX_N];
    int zeroCount = 0;

    // Đưa vị trí khởi đầu vào hàng đợi
    queueX[rear] = startX;
    queueY[rear] = startY;
    rear++;
    visited[startX][startY] = true;

    // BFS để tìm toàn bộ khu vực chứa booth 0 và tần suất booth xung quanh
    while (front < rear) {
        int x = queueX[front];
        int y = queueY[front];
        front++;

        // Lưu tọa độ của booth 0
        zerosX[zeroCount] = x;
        zerosY[zeroCount] = y;
        zeroCount++;

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

            if (isValid(nx, ny)) {
                if (map[nx][ny] == 0 && !visited[nx][ny]) {
                    queueX[rear] = nx;
                    queueY[rear] = ny;
                    rear++;
                    visited[nx][ny] = true;
                } else if (map[nx][ny] > 0) {
                    freq[map[nx][ny]]++;
                }
            }
        }
    }

    // Xác định loại booth có tần suất cao nhất xung quanh
    int maxFreq = 0, boothType = 0;
    for (int i = 1; i <= 5; ++i) {
        if (freq[i] > maxFreq || (freq[i] == maxFreq && i > boothType)) {
            maxFreq = freq[i];
            boothType = i;
        }
    }

    // Thay thế tất cả các booth 0 trong khu vực thành loại booth đã chọn
    for (int i = 0; i < zeroCount; ++i) {
        map[zerosX[i]][zerosY[i]] = boothType;
    }
}

// BFS để đếm số lượng khu vực dịch vụ
void countServiceAreas(int x, int y, int boothType) {
    int queueX[MAX_N * MAX_N], queueY[MAX_N * MAX_N];
    int front = 0, rear = 0;

    queueX[rear] = x;
    queueY[rear] = y;
    rear++;
    visited[x][y] = true;

    while (front < rear) {
        int cx = queueX[front];
        int cy = queueY[front];
        front++;

        for (int i = 0; i < 4; ++i) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];

            if (isValid(nx, ny) && !visited[nx][ny] && map[nx][ny] == boothType) {
                queueX[rear] = nx;
                queueY[rear] = ny;
                rear++;
                visited[nx][ny] = true;
            }
        }
    }
}

int main() {
    int T;
    cin >> T;

    for (int t = 1; t <= T; ++t) {
        cin >> n;

        // Đọc dữ liệu bản đồ
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                cin >> map[i][j];
                visited[i][j] = false;
            }
        }

        // Thay thế các booth 0
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (map[i][j] == 0 && !visited[i][j]) {
                    replaceZeros(i, j);
                }
            }
        }

        // Đếm số lượng khu vực dịch vụ
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                visited[i][j] = false;
            }
        }

        int areaCount = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (!visited[i][j]) {
                    areaCount++;
                    countServiceAreas(i, j, map[i][j]);
                }
            }
        }

        // In kết quả
        cout << "Case #" << t << endl;
        cout << areaCount << endl;
    }

    return 0;
}