CleaningRobot

package cleaningrobot;

import java.util.Scanner;

public class cleaningrobot {
	static int arr[][], n, m, T, visited[][], dist[][], min, check[];
	static int qx[] = new int[200000], qy[] = new int[200000], frontx, rearx, fronty, reary;
	static int dx[] = {-1,0,1,0};
	static int dy[] = {0,1,0,-1};
	static int dirX[], dirY[], robotX, robotY, index;
	
	static void init(){
		frontx = rearx = fronty = reary = -1;
		
	}
	static boolean isEmtyx(){
		if(frontx == rearx) return true;
		return false;
	}
	static boolean isEmtyy(){
		if(fronty == reary) return true;
		return false;
	}
	static void enQueuex(int e){
		rearx ++;
		qx[rearx] = e;
	}
	static void enQueuey(int e){
		reary ++;
		qy[reary] = e;
	}
	static int deQueuex(){
		if(!isEmtyx()){
			frontx ++;
			return qx[frontx];
		}
		return -1;
	}
	static int deQueuey(){
		if(!isEmtyy()){
			fronty ++;
			return qy[fronty];
		}
		return -1;
	}
	static boolean check(int x, int y){
		if(x<0 || x>=n || y<0 || y>=m)return false;
		return true;
	}
	
	static void bfs(int i, int j, int curDir){
		visited[i][j] = 1;
		enQueuex(i);
		enQueuey(j);
		while(!isEmtyx() && !isEmtyy()){
			int x = deQueuex();
			int y = deQueuey();
			for(int k=0; k<4; k++){
				int tx = x + dx[k];
				int ty = y + dy[k];
				if(check(tx, ty)){
					if(arr[tx][ty] != 2 && visited[tx][ty] == 0){
						visited[tx][ty] = visited[x][y] + 1;
						enQueuex(tx);
						enQueuey(ty);
					}
				}
			}
		}
		for(int z=curDir + 1; z<index; z++){
			if(visited[dirX[z]][dirY[z]]!=0){
				dist[curDir][z] = visited[dirX[z]][dirY[z]] - 1;
				dist[z][curDir] = dist[curDir][z];
			}
			else{
				dist[curDir][z] = -1;
				dist[z][curDir] = -1;
			}
		}
	}
	static void backtrack(int curDir, int numDir, int d){
		if(numDir == index - 1 ){
			if(d<min) min = d;
			return;
		}
		if(d>min)
			return;
		for(int i=1; i<index; i++){
			if(check[i] == 0 && dist[curDir][i] > 0){
				check[i] = 1;
				backtrack(i, numDir + 1, d + dist[curDir][i]);
				check[i] = 0;
			}
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		for(int t=1; t<=T; t++){
			n = sc.nextInt();
			m = sc.nextInt();
			arr = new int[n][m];
			dirX = new int[12];
			dirY = new int[12];
			index = 1;
			for(int i=0; i<n; i++){
				for(int j=0; j<m; j++){
					arr[i][j] = sc.nextInt();
					if(arr[i][j] == 3){
						robotX = i;
						robotY = j;
					}
					if(arr[i][j] == 1){
						dirX[index] = i;
						dirY[index] = j;
						index++;
					}
				}
			}
			dist = new int[12][12];
			//duong di tu robot den cac vet ban
			init();
			visited = new int[n][m];
			bfs(robotX, robotY, 0);
			
			//duong di tu cac vet ban den nhau
			
			for(int i=1; i<index; i++){	
				init();
				visited = new int[n][m];
				bfs(dirX[i], dirY[i], i);
			}
			min = Integer.MAX_VALUE;
			check = new int[index];
			backtrack(0, 0, 0);
			if(min != Integer.MAX_VALUE){
				System.out.println("Case #"+t+"\n"+min);
			}
			else{
				System.out.println("Case #"+t+"\n"+-1);
			}
		}
	}

}