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];
void findMaxField(int x, int y){

	frQueue.reset();
	fcQueue.reset();

	frQueue.enQueue(x);
	fcQueue.enQueue(y);

	check[x][y] = 1;

	cnt[arr[x][y]]++;
    while(frQueue.is_Empty() == false){
        int cr = frQueue.deQueue();
        int cc = fcQueue.deQueue();

		cnt[arr[cr][cc]]++;

        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 && arr[row][col] == arr[x][y]){
				cnt[arr[x][y]]++;
                check[row][col] = 1;
                frQueue.enQueue(row);
                fcQueue.enQueue(col);
            }
        }
	}
}
void BFS(int x, int y){
    rQueue.reset();
    cQueue.reset();

    visited[x][y] = true;
    rQueue.enQueue(x);
    cQueue.enQueue(y);
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			check[i][j] = false;
		}
	}
    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){
				if(arr[nr][nc] == 0){
					visited[nr][nc] = true;
					rQueue.enQueue(nr);
					cQueue.enQueue(nc);
				}else{
					if(check[nr][nc] == 0){
						findMaxField(nr, nc);
					}
				}
            }
        }
    }
	int ans = 0;
	int index = 0;
	for(int i = 0; i < 6; i++){
		if(ans <= cnt[i]){
			ans = cnt[i];
			index = i;
		}
	}
	rQueue.resetFront();
	cQueue.resetFront();
	while(rQueue.is_Empty() == false){
		int a = rQueue.deQueue();
		int b = cQueue.deQueue();
		map[a][b] = 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){
					for(int k = 0; k < 6; k++){
						cnt[k] = 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;
}