Untitled

#include <iostream> 

using namespace std;

int T, N, M;
int arr[105][105];
int visited[105][105];
int posX[10001];
int posY[10001];
int cnt;
int map[10001][10001];
int ans, minA;
int check[10000];

class Queue{
    int front, rear;
    int q[1000000];
    public:
        Queue();
        void enQueue(int value);
        int deQueue();
        void reset();
        bool is_Empty();
};

Queue::Queue(){
    front = rear = -1;
}
void Queue::enQueue(int value){
    q[++rear] = value;
}
int Queue::deQueue(){
    return q[++front];
}
bool Queue::is_Empty(){
    if(front == rear)
        return true;
    return false;
}
void Queue::reset(){
    front = rear = -1;
}

Queue rQueue, cQueue;

int X[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int Y[8] = {-1, 1, -2, 2, -2, 2, -1, 1};

void BFS(int x){
    for(int i = 0 ; i < N; i++){
        for(int j = 0; j < M; j++){
            visited[i][j] = 0;
        }
    }
    int a = posX[x];
    int b = posY[x];

    rQueue.reset();
    cQueue.reset();

    visited[a][b] = 1;

    rQueue.enQueue(a);
    cQueue.enQueue(b);

    while(!rQueue.is_Empty()){
        int cr = rQueue.deQueue();
        int cc = cQueue.deQueue();
        for(int i = 0; i < 8; i++){
            int nr = cr + X[i];
            int nc = cc + Y[i];
            if(nr >= 0 && nr < N && nc >= 0 && nc < M && visited[nr][nc] == 0){
                visited[nr][nc] = visited[cr][cc] + 1;
                rQueue.enQueue(nr);
                cQueue.enQueue(nc);
            }
        }
    }
    for(int i = 0; i < cnt; i++){
        if(i != x){
            int tmpX = posX[i];
            int tmpY = posY[i];
            map[x][i] = visited[tmpX][tmpY] - 1;
            map[i][x] = visited[tmpX][tmpY] - 1;
        }
    }
}

void backtrack(int k, int count){
    if(minA <= ans){
        return;
    }
    if(count == cnt){
        if(minA > ans){
            minA = ans;
        }
        return;
    } 
    for(int i = 1; i < cnt; i++){
        if(check[i] == 0 && map[k][i] != 0){
            ans += map[k][i];
            check[i] = 1;
            backtrack(i, count + 1);
            ans -= map[k][i];
            check[i] = 0;
        }
    }
}

int main(){
    freopen("input.txt", "rt", stdin);
    cin >> T;
    for(int tc = 1; tc <= T; tc++){
        cin >> N >> M;
        cnt = 1;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                cin >> arr[i][j];
                if(arr[i][j] == 3){
                    posX[0] = i;
                    posY[0] = j;
                }
                if(arr[i][j] == 1){
                    posX[cnt] = i;
                    posY[cnt] = j;
                    cnt++;
                }
            }
        }
        for(int i = 0; i < cnt; i++){
            for(int j = 0; j < cnt; j++){
                map[i][j] = 0;
            }
        }
        for(int i = 0; i < cnt; i++){
            BFS(i);
        }
        for(int i = 0; i < cnt; i++){
            check[i] = 0;
        }
        ans = 0;
        minA = 1000000;
        backtrack(0, 1);
        cout << "Case #" << tc << endl;
        cout << minA << endl;
    }
    return 0;
}