Untitled

 avatar
unknown
plain_text
2 years ago
2.3 kB
2
Indexable
#include<iostream>
using namespace std;
int N, G;
int M[25][25];
int visit[25][25];
int A[6][2];
int visit_mv[6];
int f=-1, r=-1;
int Qx[100000];
int Qy[100000];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
void push(int x,int y)
{
	f++;
	Qx[f] =x;
	Qy[f] =y;
}
void pop(int &x,int &y)
{
	r++;
	x= Qx[r];
	y= Qy[r];
}
void bfs(int x,int y)
{
	f=r=-1;
	push(x,y);
	visit[x][y] =0;
	while(f != r)
	{
		pop(x,y);
		for(int i=0; i<4; i++)
		{
			int xx=  x +dx[i];
			int yy = y+ dy[i];
			if(xx>=1 && xx <=N && yy >=1 && yy <=N && visit[xx][yy]==-1 && M[xx][yy] != 0)
			{
				push(xx,yy);
				visit[xx][yy] = visit[x][y] +1;
			}

		}
	}

}

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

int main()
{
	freopen("Text.txt" , "r" , stdin);
	int t;
	cin >> t;
	for(int stt=1; stt<=t; stt++)
	{
		cin >> N >> G;
		for(int i=1; i<=G; i++)
		{
			cin >> A[i][0] >> A[i][1];
		}
		for(int i=1; i<=N; i++)
		{
			for(int j=1; j<=N; j++)
			{
                cin >> M[i][j];
			}
		}
		for(int i=1; i<=G; i++)
		{
			M[A[i][0]][A[i][1]]=2;
		}
		/////////////////////////
		int count_mv, s_max;
		int max_mv=0;
		int min_s =10000;
		for(int i=1; i<=N; i++)
		{
			for(int j=1; j<=N; j++)
			{
				if(M[i][j] ==1 ){
					count_mv =0; s_max =0;
					reset();
					bfs(i,j);
					for(int q=1; q<=G; q++)
					{
						if(visit[A[q][0]][A[q][1]]  != -1){
							count_mv ++;
						}
						if(visit[A[q][0]][A[q][1]]  > s_max){
							s_max = visit[A[q][0]][A[q][1]];
						}
					}
					//////////////////////////
					if(count_mv > max_mv || (count_mv == max_mv && s_max < min_s))
					{
						max_mv = count_mv; min_s = s_max;
						for(int k=1; k<=4; k++)
						{
							visit_mv[k]= visit[A[k][0]][A[k][1]];
						}
					}
				}
			}
		}
		//////////////////////////////////////////////////////
		if(max_mv == G)     cout << "Case #" << stt <<endl << min_s << endl;
		else if(max_mv ==0) cout << "Case #" << stt << endl << "-1" << endl;
		else {
			cout << "Case #" << stt << endl << min_s<< endl;
			for(int i=1; i<=G; i++)
			{
				if(visit_mv[i] == -1)
				{
					cout << A[i][0] << " " << A[i][1] << endl;
				}
			}
		}
	}
	return 0;
}
Editor is loading...