Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.2 kB
1
Indexable
Never
#include<iostream>

using namespace std;
#define size 1000
int N, G;
int map[25][25];
int gold[4][2];
int visit[25][25];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int queueX[size];
int queueY[size];
int front=-1;
int rear=-1;
int cnt[5];
int be;
int ans=0;
bool isEmpty(){
	return front==rear;
}
void push(int x, int y){
	if(rear==size-1) rear=-1;
	rear++;
	queueX[rear]=x;
	queueY[rear]=y;

}
int popX(){
	if(front==size-1) front=-1;
	front++;
	return queueX[front];
}
int popY(){
	if(front==size-1) front=-1;
	front;
	return queueY[front];
}

void bfs(int x, int y){
	visit[x][y]=0;
	front=rear =-1;
	push(x, y);
	while (!isEmpty())
	{
		int a; int b;
		a=popX(); 
		b=popY();
		for(int i=0; i<4; i++){
			int h=a+dx[i];
			int c= b+dy[i];
			if( h>=1 && h<=N && c>=1 && c <=N && map[h][c] != 0 && visit[h][c] == -1){

				visit[h][c]=visit[a][b]+1;
				push(h,c);
			}

		}

	}
}


void reset(){
	for(int i=1; i<=N; i++){
		for(int j=1;j<=N; j++){
			visit[i][j]=-1;
		}
	}
}


int main()
{
	int T;

	freopen("Text.txt", "r", stdin);
	cin >> T;

	for(int test_case = 1; test_case <= T; ++test_case)
	{
		cin>>N>>G;
		
		
		for(int i=0; i<G; i++){
			int a;
			int b;
			cin>>a;
			cin>>b;
			gold[i][0]=a;
			gold[i][1]=b;
			
		}

		for(int i=1; i<=N;i++){
			for(int j=1; j<=N; j++){
				cin>>map[i][j];
			}
		}

		for(int i= 0; i<G; i++){
			map[gold[i][0]][gold[i][1]]= 2;
		}

		be=10000;
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= N; j++)
			{
				if(map[i][j] == 1) {
					reset();

					bfs(i,j);

					int lon = 0, tmpMax = 0;

					for(int h = 0; h<G; h++){
						lon+=visit[gold[h][0]][gold[h][1]];
					}

					if(be>=lon) 
					{ 
						be = lon;

						for(int h = 0; h<G; h++){
							if (visit[gold[h][0]][gold[h][1]] > tmpMax)
							{
								tmpMax = visit[gold[h][0]][gold[h][1]];
							}
						}
						if (tmpMax > ans)
						{
							ans = tmpMax;
						}
					}	
				}
			}
		}

		cout << "Case #" << test_case  <<endl<< ans << endl;
	}
	return 0;//Your program should return 0 on normal termination.
}