Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.6 kB
3
Indexable
Never
#include <iostream>
#define N 505

using namespace std;
int n,m;
int a[N][N];

int stx,sty,fx,fy;
bool ans;
int hx[]={0,-1,0,1};
int hy[]={-1,0,1,0};
int dd[N][N];
int sx[N];
int sy[N];
int dau,cuoi;
int bfs(int x,int y)
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)dd[i][j]=0;
	 dau=1;
	 cuoi=0;
	 {
	sx[++cuoi]=x;
	sy[cuoi]=y;
	dd[x][y]=1;
	 }
	 int cnt =0;
	 int ln=0;
	while(dau<=cuoi)
	{
		int u=sx[dau];
		int v=sy[dau];
		dau++;
		for(int i=0;i<4;i++)
		{
			int xx=u+hx[i];
			int yy=v+hy[i];
			if(xx>0&&xx<=n&&yy>0&&yy<=n&&dd[xx][yy]==0&&a[xx][yy]>0)
				{
				dd[xx][yy]=dd[u][v]+1;
				sx[++cuoi]=xx;
				sy[cuoi]=yy;
				if(a[xx][yy]==2)
					{
						cnt++;
						if(dd[xx][yy]>ln)ln=dd[xx][yy];
				}
			}

		}
		
	}
	if(cnt<m)ln=10001;
	return ln-1;
}

void doc()
{
	ans=true;
	
	cin>>n>>m;
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)a[i][j]=dd[i][j]=0;
	int u,v;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v;
		a[u][v]=2;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			{
				if(a[i][j]==2)cin>>u;
				else 
				cin>>a[i][j]; 	
				//cout<<a[i][j]<<" ";
			}
		//cout<<"\n";
	}
	
}
int TC;
int main()
{
	//freopen("input.txt","r",stdin);
	
	cin>>TC;
	for(int tc=1;tc<=TC;tc++)
	{
		cout<<"Case #"<<tc<<"\n";
		doc();
		int ans=10000;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)if(a[i][j]==1)
			{
				int kq=bfs(i,j);
				//cout<<i<<" "<<j<<" "<<kq<<"\n";
				if(kq<ans)ans=kq;

			}
			if(ans==10000)ans=-1;
			cout<<ans<<"\n";
	}
	
		return 0;
}