Untitled

#include <iostream>

using namespace std;
//Bài toán cleaning robot: tìm số bước đi ngắn nhất để con robot làm sạch hết các ô gạch bẩn
int dx[] = {-1,0,0,1};
int dy[] = {0,-1,1,0};
bool visit[300][300]={false},check[11]={false};
int matrix[300][300], kq=1000000,sum_step=0, dis[20][20],n,m,k;
struct cell
{
    int x, y;
    int dis;
    cell() {}
    cell(int x, int y, int dis) : x(x), y(y), dis(dis) {}
};

cell queue[9000009];
cell dirty[11];
int Vao =0;
int Ra = 0;

void Init () 
{
    Vao = 0; 
    Ra = 0;    
}
cell peek() {
   return queue[Ra];
}

bool isempty() {  
	if(Vao==Ra){	
		return 1;
	}
	return 0;
} 
cell pop() {
  return queue[Ra++];
}

void push( cell x) {
   queue[Vao++] = x;
}

bool isInside(int x, int y, int N,int M)
{
    if (x >= 1 && x <= N && y >= 1 && y <= M)
        return true;
    return false;
}

int BFS(int start_x, int start_y,int end_x, int end_y)
{        
   Init();
    // push starting position of knight with 0 distance
    push(cell(start_x, start_y, 0));
 
    cell t;
    int x, y;	
 
    // make all cell unvisited
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            visit[i][j] = false;
 
    // visit starting state
    visit[start_x][start_y] = true;
 
    // loop untill we have one element in queue
    while (!isempty())
    {
        t = pop();
 
        // if current cell is equal to target cell,
        // return its distance
		if (t.x == end_x && t.y == end_y)
            return t.dis;
 
        // loop for all reachable states
        for (int i = 0; i < 4; i++)
        {
            x = t.x + dx[i];
            y = t.y + dy[i];
 
            // If reachable state is not yet visited and
            // inside board, push that state into queue
            if (isInside(x, y, n, m) && !visit[x][y] && matrix[x][y]!=2) {
                visit[x][y] = true;				
                push(cell(x, y, t.dis + 1));
            }
        }
    }
	return -1;
}


void backtracking(int count, int parent, int sum){
	int i;
	if(count==k){
		if(kq>sum) kq=sum;
		return;
	}else {
		for(i=1;i<k;i++){			
			if(check[i]==0 && kq>sum){
				check[i] = true;
				count++;				
				backtracking(count, i, sum+dis[parent][i]);	
				check[i] = false;
				count--;
			}
		}
	}
}
 
int main ()
{     
	ios:: sync_with_stdio(false);	
	int tc,check_move;
	//freopen("input.txt","r", stdin);   
	cin>>tc;
	
	for(int t=1;t<=tc;t++){		
		k=1;
		check_move = 1;
		kq = 10000000;
		//Nhập vào kích thước ma trận
		cin>>n;
		cin>>m;
		//Nhập vào ma trận bản đồ
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>matrix[i][j];
				if(matrix[i][j]==3){
					//Lưu lại vị trí con robot
					dirty[0].x = i;
					dirty[0].y = j;					
				}else if(matrix[i][j]==1){
					//Lưu lại vị trí các ô gạch bẩn
					dirty[k].x = i;
					dirty[k].y = j;
					k++;
				}
			}
		}
		cout<<"Case #"<<t<<endl;
		//Dùng BFS tính trước ma trận khoảng cách ngắn nhất giữa các đỉnh
		for(int i=0;i<k;i++){
			for(int j=0;j<k;j++){
				if(i<j && check_move==1){
					dis[i][j] = BFS(dirty[i].x, dirty[i].y, dirty[j].x, dirty[j].y);
					dis[j][i] = dis[i][j];
					if(dis[j][i] == -1) {
						cout<<"-1"<<endl;
						check_move = 0;
						break;
					}
				}
			}
		}

		//Dùng backtracking để tìm thứ tự đi đến các ô gạch bẩn sao cho đường đi là ngắn nhất
		if(check_move==1){
			for(int i=1;i<k;i++){
				check[i] = false;
			}
			backtracking(1, 0, 0);
			cout<<kq<<endl;
		}
		
	}
//	getch();
   return 0;
}