Untitled

package Cleaning_Robot;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int n, m, res;
	static int[][] a = new int[105][105], kc;
	static int x, y;
	static int[] xdirty = new int[15], ydirty = new int[15], visit, hvi;
	static int dirty, tuong;
	static int[] dx = { 0, 1, 0, -1 }, dy = { 1, 0, -1, 0 };
	static int[] qx = new int[10005], qy = new int[10005];
	
	public static void BFS(){
		for(int i = 0; i < dirty-1; i++){
			int[][] lan = new int[n][m];
			int[][] visit = new int[n][m];
			
			int front = 0, rear = 0;
			qx[front] = xdirty[i]; qy[front] = ydirty[i];
			lan[xdirty[i]][ydirty[i]] = 0;
			visit[xdirty[i]][ydirty[i]] = 1;
			while(front <= rear){
				int x = qx[front];
				int y = qy[front];
				int c = lan[x][y];
				
				for(int j = 0; j < 4; j++){
					int nx = x + dx[j];
					int ny = y + dy[j];
					if(nx >= 0 && ny >= 0 && nx < n && ny < m && a[nx][ny] != 2 && visit[nx][ny] == 0){
						rear++;
						qx[rear] = nx;
						qy[rear] = ny;
						lan[nx][ny] = c+1;
						visit[nx][ny] = 1;
					}
				}
				
				front++;
			}
			for(int j = i+1; j < dirty; j++){
				kc[i][j] = lan[xdirty[j]][ydirty[j]];
				kc[j][i] = lan[xdirty[j]][ydirty[j]];
			}
			
			
		}
	}
	
	public static boolean cant(){
		for(int i = 0; i < dirty; i++){
			for(int j = 0; j < dirty; j++){
				if(i != j && kc[i][j]==0){
					return true;
				}
			}
		}
		return false;
	}

	public static void backTrack(int k, int length) {
		if(length >= res){
			return;
		}
		if(k==dirty){
			res = Math.min(res, length);
			return;
		}
		for(int i = 1; i < dirty; i++){
			if(visit[i] == 0){
				hvi[k] = i;
				visit[i] = 1;
				int distan = kc[hvi[k]][hvi[k-1]];
				backTrack(k+1, length+distan);
				visit[i] = 0;
			}
		}
	}

	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("input.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		Scanner scanner = new Scanner(System.in);
		int test = scanner.nextInt();
		for (int t = 1; t <= test; t++) {
			n = scanner.nextInt();
			m = scanner.nextInt();
			dirty = 0; 
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					a[i][j] = scanner.nextInt();
					if (a[i][j] == 3) {
						xdirty[dirty] = i;
						ydirty[dirty] = j;
						dirty++;
					}
				}
			}
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (a[i][j] == 1) {
						xdirty[dirty] = i;
						ydirty[dirty] = j;
						dirty++;
					}
				}
			}
			res = Integer.MAX_VALUE;
			
			visit = new int[dirty];
			hvi = new int[dirty];
			kc = new int[dirty][dirty];
			BFS();
			
			if(cant()){
				System.out.println("Case #" + t + "\n-1");
			}else{
				backTrack(1, 0);
				System.out.println("Case #" + t + "\n" + res);
			}
			
		}
		scanner.close();
	}
}