Untitled

Quân mã

Trong một bàn cờ NxM.



Tìm số lần đi tối thiểu để quân mã ăn hết quân địch.



Quân mã có thể di chuyển xung quanh theo 8 hướng .(H1)



H1



Example : test case 1



Quân mã mất 3 lần di chuyển để ăn hết quân địch . (2,3) -> (3,5) -> (4,3)



H2



Input : dòng đầu tiên là số lương test case



            Dòng 2 là kích thước của bàn cờ



Tiếp theo là bàn cờ :



3 là vị trí xuất phát của quân mã



1 là vị trí quân địch



0 là vị trí trống.



Quân mã có thể di chuyển trên tất cả các vị trí trên bàn cờ (0,1,3).



Output:



In ra số lần di chuyển nhỏ nhất để quân mã ăn hết quân địch.



Sample input:



2



5 7



0 0 0 0 0 0 0



0 3 0 0 0 0 0



0 0 0 1 0 0 0



0 0 0 0 0 1 0



0 0 0 1 0 0 0



10 10



1 0 0 0 0 0 0 0 0 0



0 0 0 0 0 0 0 0 0 0



0 0 0 0 0 0 0 0 0 0



0 0 0 0 0 0 0 1 0 0



0 1 0 0 0 0 0 0 0 0



0 0 0 0 0 0 0 0 0 0



0 0 0 0 0 0 3 0 0 0



0 0 0 0 0 0 0 0 0 0



0 0 0 0 0 0 0 0 0 0



0 0 0 0 0 0 0 0 0 1



Sample output:



Case #1

3

Case #2

12



Code: 
#include<iostream>
#define max 10005
using namespace std;
int n,m,h; 
int map[105][105];
int diem_ban[2][105];
int visit[105][105]; // xem diem nao da di qua
int di[8]={-2, -1, 1, 2, 2, 1, -1, -2 };
int dj[8]={ 1,  2, 2, 1,-1,-2, -2, -1 };
int queuex[100000];
int queuey[100000];
int front= -1;
int	rear=-1;
int dis[105][105]; // ma tran ke khoang cach giua cac diem ban
int d[105][105]; // tinh khoang cach
int check[105];
int cnt;
int tong,kq;

void pushq(int x,int y){
	if(rear == max-1) rear =-1;
	rear++;
	queuex[rear]=x;
	queuey[rear]=y;
}

void pop(){
	if(front == max-1) front =-1;
	front++;

}
bool IsEmpty(){
	return front == rear;
}

bool checkIn(int i ,int j){
	if(i>=0 && i<n && j>= 0 && j<m) return true;
	return false;
}
void resetvisit(){
	for(int i=0; i<n;i++){
			for(int j =0; j< m; j++){
				visit[i][j] =0;
				d[i][j] =0;
			}
	}
}
void resetcheck(){
	for(int i=0; i<h;i++){
		check[i]=0;
	}
}
int bfs(int ibd, int jbd, int iket, int jket){
	front = rear =-1;
	pushq(ibd,jbd);
	resetvisit();
	visit[ibd][jbd] = 1;
	while(!IsEmpty()){
		pop();
		int i1 = queuex[front];
		int j1 = queuey[front];
		for(int k=0; k<8;k++){
			int i2 = i1 + di[k];
			int j2 = j1 + dj[k];
			if(checkIn(i2,j2)==true && visit[i2][j2]==0){
			//	visit[i2][j2] = visit[i1][j1]+1;
				d[i2][j2] = d[i1][j1]+1;
				visit[i2][j2] =1;
				if(i2 == iket && j2 == jket) return d[i2][j2];
				pushq(i2,j2);
			}
		}
	}
	return -1;
}
void backtrack(int  i){
		if(cnt ==h-1) {
			if(kq>tong) kq = tong;
			return;
		}
		int nho = max;

		
		for(int j =1; j< h; j++){
			if(check[j] ==0 && kq>tong ){
				check[j] =1;
				nho =dis[i][j];
				cnt++;
				tong += nho;
				backtrack(j);
				check[j] =0;
				tong -= nho;
				cnt--;

			}
		}
		
}
		

int main(){
	//freopen("Text.txt", "r", stdin);
	int test;
	cin >> test;
	for(int tc =1; tc<=test; tc++){
		cin >> n >>m;
		h=1;
		for(int i=0; i<n;i++){
			for(int j =0; j< m; j++){
				cin >> map[i][j];
				if(map[i][j] == 3){
					diem_ban[0][0]=i;
					diem_ban[1][0]=j;
				}
				else if(map[i][j] == 1){
					diem_ban[0][h]=i;
					diem_ban[1][h]=j;
					h++;
				}
			}
		}

		cout << "Case #" << tc << endl;
	
		
		//bfs de tim khoang cach den cac diem ban
		for(int i=0; i<h;i++){
					
			for(int j =i+1; j< h; j++){
				dis[i][j] = bfs(diem_ban[0][i], diem_ban[1][i], diem_ban[0][j], diem_ban[1][j]);
			
				dis[j][i] = dis[i][j];
				
			}
		}
		cnt =0;
		tong =0;
		kq = max;
		resetcheck();
		check[0] =1;
		backtrack(0);
		cout << kq << endl;


	}
		return 0;
}