Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.8 kB
1
Indexable
Never
#include<iostream>
#define max 1000000
using namespace std;
int queuex[100];
int queuey[100];
int front= -1;
int	rear=-1;
int n,m;
int map[25][25];
int visit[25][25];
int d[25][25];
int toado[4][2];
int ans;
int dx[4]={1, -1, 0 ,0};
int dy[4]={0, 0 , 1, -1};
int pushq(int x,int y){
	if(rear == max-1) rear =-1;
	rear++;
	queuex[rear]=x;
	queuey[rear]=y;
}

int popx(){
	if(front == max-1) front =-1;
	front++;
	return queuex[front];
}
int popy(){
	if(front == max-1) front =-1;
	return queuey[front];
}
bool IsEmpty(){
	if(front == rear)
		return true;
	return false;
}

void reset(){
	for(int i=0; i < n; i++){
			for(int j= 0; j < n; j++){
				visit[i][j]=0;
			}
	}
}
void Try(int i, int j){
	int duongdi=0;
	int somo=0;
	if(ans > duongdi) ans =duongdi;
	pushq(i,j);
	visit[i][j] = 1;
	d[i][j]=0;

	while(!IsEmpty()){
		for(int h=0; h < 4 ; h++){
		int i1= popx()+dx[h];
		int j1 = popy()+dy[h];
		if(i1 >= 0  && i1 <n && j1>=0 && j1 <n && map[i1][j1] == 1 && visit[i1][j1] == 0){
			d[i1][j1] = d[i][j] +1;
			for(int k =0; k<m; k++){
				if(i1 == toado[k][0] && j1 == toado[k][1]){
					duongdi += d[i1][j1] ;
					somo++;
				}
				if(somo == m)return;
			}
			pushq(i1,j1);
			visit[i1][j1]=1;
		}
		}
	}
}

int main(){
	freopen("Text.txt", "r", stdin);
	int test;
	cin >> test;
	
	for(int tc= 1; tc <= test; tc++){
		cin >> n>>m;

		for(int i=0; i < m; i++){
			for(int j= 0; j < 2; j++){
				cin >> toado[i][j];
			}
		}
		for(int i=0; i < n; i++){
			for(int j= 0; j < n; j++){
				cin >> map[i][j];
			}
		}
		ans =1000000;
		for(int i=0; i < n; i++){
			for(int j= 0; j < n; j++){
				reset();
				if(map[i][j] == 1){
					Try(i,j);
				}
			}
		}
		
		cout << "Case #" << tc << endl;
		cout << ans << endl;
		}
	return 0;
}