Untitled

#include <iostream>

using namespace std;

int T, N;
int arr[105][105];

class Queue{
    int front, rear;
    int q[10000000];
public:
    Queue();
    void enQueue(int value);
    int deQueue();
    void reset();
    bool is_Empty();
    void resetFront();
};
Queue::Queue(){
    front = rear = -1;
}
void Queue::enQueue(int value){
    q[++rear] = value;
}
int Queue::deQueue(){
    return q[++front];
}
void Queue::reset(){
    front = rear = -1;
}
bool Queue::is_Empty(){
    return front == rear;
}
void Queue::resetFront(){
    front = -1;
}
int check[105][105];
int X[4] = {-1, 1, 0, 0};
int Y[4] = {0, 0, 1, -1};
int cnt[6];
bool visited[105][105];
Queue rQueue, cQueue;
Queue frQueue, fcQueue;
int map[105][105];
int tmp[105][105];
int findMaxField(int x, int y){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            check[i][j] = 0;
        }
    }
    frQueue.reset();
    fcQueue.reset();
    check[x][y] = 1;
    int count = 1; 
    frQueue.enQueue(x);
    fcQueue.enQueue(y);
    while(frQueue.is_Empty() == false){
        int cr = frQueue.deQueue();
        int cc = fcQueue.deQueue();
        for(int i = 0; i < 4; i++){
            int row = cr + X[i];
            int col = cc + Y[i];
            if(row >= 0 && row < N && col >= 0 && col < N && check[row][col] == 0 && tmp[row][col] == tmp[cr][cc]){
                check[row][col] = 1;
                frQueue.enQueue(row);
                fcQueue.enQueue(col);
                count++;
            }
        }   
    }
    return count;
}
void BFS(int x, int y){
    rQueue.reset();
    cQueue.reset();
    visited[x][y] = true;
    rQueue.enQueue(x);
    cQueue.enQueue(y);
    while(rQueue.is_Empty() == false){
        int cr = rQueue.deQueue();
        int cc = cQueue.deQueue();
        for(int i = 0; i < 4; i++){
            int nr = cr + X[i];
            int nc = cc + Y[i];
            if(nr >= 0 && nr < N && nc >= 0 && nc < N && visited[nr][nc] == false && arr[nr][nc] == 0){
                visited[nr][nc] = true;
                rQueue.enQueue(nr);
                cQueue.enQueue(nc);
            }
        }
    }

    for(int i = 0; i < 6; i++){
        cnt[i] = 0;
    }
    for(int k = 5; k >= 1; k--){
        rQueue.resetFront();
        cQueue.resetFront();
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                tmp[i][j] = arr[i][j];
            }
        }
        while(rQueue.is_Empty() == false){
            int row = rQueue.deQueue();
            int col = cQueue.deQueue();
            tmp[row][col] = k;
        }
        cnt[k] = findMaxField(x, y);
    }
    int ans = 0;
    int index;
    for(int i = 0; i < 6; i++){
        if(cnt[i] >= ans){
            ans = cnt[i];
            index = i;
        }
    }
    rQueue.resetFront();
    cQueue.resetFront();
    while(rQueue.is_Empty() == false){
        int r = rQueue.deQueue();
        int c = cQueue.deQueue();
        map[r][c] = index;
    }
}

void demvung(int x, int y){
    rQueue.reset();
    cQueue.reset();
    visited[x][y] = true;
    rQueue.enQueue(x);
    cQueue.enQueue(y);
    while(rQueue.is_Empty() == false){
        int cr = rQueue.deQueue();
        int cc = cQueue.deQueue();
        for(int i = 0; i < 4; i++){
            int nr = cr + X[i];
            int nc = cc + Y[i];
            if(nr >= 0 && nr < N && nc >= 0 && nc < N && visited[nr][nc] == false && map[nr][nc] == map[cr][cc]){
                visited[nr][nc] = true;
                rQueue.enQueue(nr);
                cQueue.enQueue(nc);
            }
        }
    }
}
int main(){
    freopen("input.txt", "rt", stdin);
    cin >> T;
    for(int tc = 1; tc <= T; tc++){
        cin >> N;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                cin >> arr[i][j];
                visited[i][j] = false;
            }
        }
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(visited[i][j] == false && arr[i][j] == 0){
                    BFS(i, j);
                }   
            }
        }
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                visited[i][j] = false;
                if(arr[i][j] != 0){
                    map[i][j] = arr[i][j];
                }
            }
        }
        int res = 0;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(visited[i][j] == false){
                    res++;
                    demvung(i, j);
                }
            }
        }
        cout << "Case #" << tc << endl;
        cout << res << endl;
    }
    return 0;
}