Untitled

mail@pastecode.io avatar
unknown
plain_text
5 months ago
1.9 kB
1
Indexable
Never
#include <iostream>
#define N 201
#define oo 2000000009
using namespace std;

int min(int u, int v)
{
	if(u>v)return v;
	return u;
}
int max(int u, int v)
{
	if(u>v)return u;
	return v;
}
int n,m;
int sr,sc,fr,fc;
char a[N][N];

int sx[N*N],sy[N*N],sz[N*N];
int hx[]={0,-1,0,1};
int hy[]={-1,0,1,0};
int dd[N][N][5];

void doc()
{
	cin>>m>>n;
	cin>>sc>>sr>>fc>>fr;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			{
				cin>>a[i][j];
				for(int l=0;l<4;l++)dd[i][j][l]=0;
		}

	
}

void bfs(int u,int v)
{
	int dau=1;
	int cuoi=0;
	for(int i=0;i<4;i++)
	{
		int xx=u,yy=v,zz=i;
		do
		{
			dd[xx][yy][zz]=1;
			sx[++cuoi]=xx;
			sy[cuoi]=yy;
			sz[cuoi]=zz;
			xx=xx+hx[zz];
			yy=yy+hy[zz];
		}while(xx>0&&xx<=n&&yy>0&&yy<=m&&a[xx][yy]=='0');
	}
	while(dau<=cuoi)
	{
		int x=sx[dau];
		int y=sy[dau];
		int z=sz[dau];
		//cout<<x<<" "<<y<<" "<<z<<" "<<dd[x][y][z]<<"\n";
		dau++;
		int xx=x,yy=y,zz=z;
		do
		{
			xx=xx+hx[z];
			yy=yy+hy[z];
			if(xx>0&&xx<=n&&yy>0&&yy<=m&&dd[xx][yy][z]==0&&a[xx][yy]=='0')
			{
				dd[xx][yy][zz]=dd[x][y][z];
				sx[++cuoi]=xx;
				sy[cuoi]=yy;
				sz[cuoi]=zz;
			}
		}while(xx>0&&xx<=n&&yy>0&&yy<=m&&a[xx][yy]=='0');
		for(int i=0;i<4;i++)if(i!=z)
		{
			 xx=x+hx[i];
			 yy=y+hy[i];
			 zz=i;
			int cp=1;
			if(xx>0&&xx<=n&&yy>0&&yy<=m&&a[xx][yy]=='0')
			{
				if(dd[xx][yy][zz]==0)
				{
					dd[xx][yy][zz]=dd[x][y][z]+cp;
					sx[++cuoi]=xx;
					sy[cuoi]=yy;
					sz[cuoi]=zz;
				}else if(dd[xx][yy][zz]>dd[x][y][z]+cp)dd[xx][yy][zz]=dd[x][y][z]+cp;
			}
		}
	}
}

int main()
{
	//freopen("input.txt","r",stdin);
	int TC;
	cin>>TC;
	for(int tc =1;tc<=TC;tc++)
	{
		int ans=oo;
		doc();
		bfs(sr,sc);
		for(int i=0;i<4;i++)if(dd[fr][fc][i])ans=min(ans,dd[fr][fc][i]-1);
		if(ans==oo)ans=-1;
		cout<<ans<<"\n";
	}
	return 0;
}