Untitled

#include <bits/stdc++.h>

using namespace std;

int dx[8] = {2, 1, -1, -2, -2, -1, 1, 2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int t;
int n, m;
const int MN = 205;
int grid[MN][MN];
int cnt_qd = 0, size = 0;
int coor[MN][2];
int dist[MN][MN][MN];

void bfs(int k, int sx, int sy) {
    queue<pair<int, int>> mq;
    mq.push(make_pair(sx, sy));
    dist[k][sx][sy] = 0;
    
    while (!mq.empty()) {
        auto [x, y] = mq.front();
        mq.pop();
        
        for (int i = 0; i < 8; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (0 <= nx && nx < n && 0 <= ny && ny < m && dist[k][nx][ny] == -1) {
                mq.push(make_pair(nx, ny));
                dist[k][nx][ny] = dist[k][x][y] + 1;
            }
        }
    }
}

bool visited[MN];
int per[MN];
int ans = 1e9;

void permutation(int i, int cost) {
    if (ans < cost) {
        return;
    }
    if (i == size) {
        ans = min(ans, cost);
        return;
    }
    for (int j = 1; j < size; ++j) {
        if (visited[j]) {
            continue;
        }
        visited[j] = true;
        per[i] = j;
        int dist_ = dist[per[i - 1]][coor[per[i]][0]][coor[per[i]][1]];
        if (dist_ != -1) {
            permutation(i + 1, cost + dist_);
        }
        visited[j] = false;
    }
}

int main()
{
    cin >> t;
    for (int test_case = 1; test_case <= t; ++test_case) {
        cin >> n >> m;
        cnt_qd = 0;
        size = 0;
        
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                cin >> grid[i][j];
                
                if (grid[i][j] == 3) {
                    coor[size][0] = i;
                    coor[size][1] = j;
                }
                
                for (int k = 0; k < MN; ++k) {
                    dist[k][i][j] = -1;
                }
            }
        }
        
        bfs(size, coor[0][0], coor[0][1]);
        size++;
        
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 1) {
                    coor[size][0] = i;
                    coor[size][1] = j;
                    bfs(size, coor[size][0], coor[size][1]);
                    size++;
                }
            }
        }
        
        ans = 1e9;
        
        permutation(1, 0);
        
        cout << "Case #" << test_case << '\n';
        cout << ans << '\n';
    }
    return 0;
}