Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.3 kB
7
Indexable
Never
#include<iostream>
using namespace std;
#define INF 1000000007
int qx[100000];
int qy[100000];
int top=-1;
int bot=-1;
void push(int i,int j)
{
	bot++;
	qx[bot]=i;
	qy[bot]=j;
}
void pop(){top++;}
bool is_emty(){return top==bot;}
//-------------------------------

int N,G;
int gold[5][2];
int map[21][21];
int map_gold[4];
int vis[21][21];

int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};


void BFS(int i,int j)
{
	top=bot=-1;
	vis[i][j]=0;
	push(i,j);
	while(!is_emty())
	{
		int x = qx[top+1];
		int y = qy[top+1];
		pop();
		for(int k=0;k<4;k++)
		{
			int xx =x+dx[k];
			int yy =y+dy[k];
			if(xx>=1&&xx<=N && yy>=1&&yy<=N && map[xx][yy]!=0)
			{
				if(vis[xx][yy]==-1)
				{
					vis[xx][yy]=vis[x][y]+1;
					push(xx,yy);
				}
			}
		}
	}
}
void input()
{
	cin>>N>>G;
	for(int i=1;i<=G;i++)
	{
		int x,y;
		cin>>x>>y;
		gold[i][0]=x;
		gold[i][1]=y;
	}
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=N;j++)
		{
			vis[i][j]=-1;
			cin>>map[i][j];
		}
	}
	for(int i=1;i<=G;i++)
		map[gold[i][0]][gold[i][1]]=2;

}
void reset_vis()
{
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=N;j++)
			vis[i][j]=-1;
	}
}
int main()
{
	freopen("input.txt","r",stdin);
	int T;
	cin>>T;
	for(int tc=1;tc<=T;tc++)
	{
		input();
		//reset 
		reset_vis();
		//reset
		int gold_max=0,time_min=INF;
		for(int i=1;i<=N;i++)
		{
			for(int j=1;j<=N;j++)
			{
				int dem_gold=0,time_gold=0;
				if(map[i][j]==1)
				{
					BFS(i,j);
					for(int q=1;q<=G;q++)
					{
						if(vis[gold[q][0]][gold[q][1]]!=-1)
						{
							dem_gold++;
							time_gold=max(time_gold,vis[gold[q][0]][gold[q][1]]);
						}
					

					}

					if(dem_gold>gold_max || dem_gold==gold_max && time_gold<time_min)
					{
						gold_max=dem_gold;
						time_min = time_gold;
						for(int k=1;k<=4;k++)
							map_gold[k]=vis[gold[k][0]][gold[k][1]];
					}
					reset_vis();
				}
			}
		}
		if(gold_max==G)
			cout<<"Case #"<<tc<<endl<<time_min<<endl;
		else if(gold_max==0)
			cout<<"Case #"<<tc<<endl<<-1<<endl;
		else

		{
			cout<<"Case #"<<tc<<endl<<time_min<<endl;
			for(int i=1;i<=G;i++)
			{
				if(map_gold[i]==-1)
					cout<<gold[i][0]<<" "<<gold[i][1]<<endl;
			}
		}
		cout<<"Minh vip"<<endl;
	}
	return 0;
}
//o7t1htg8