Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.4 kB
2
Indexable
Never
#include<iostream>
using namespace std;

int t,n,m,stx,sty,ex,ey;
int front = -1;
int rear = -1;
int Qx[10000000],Qy[10000000];
char map[300][300];
int vs[300][300];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int ans;
bool checkbien(int x, int y)
{
	if (x<=0 || x>m || y <= 0 || y > n) return false;
	return true;

}


void push(int x, int y)
{
	rear ++;
	Qx[rear] = x;
	Qy[rear] = y;
}

void pop(int &x, int &y)
{
	front ++;
	x = Qx[front];
	y = Qy[front];
}

void Bfs()
{
	front = rear = -1;
	for (int i=1; i<=m; i++)
		for (int j=1; j<=n; j++) vs[i][j] = -1;
	push(stx,sty);
	vs[stx][sty] = 0;
	int x,y;
	while(front != rear)
	{
		pop(x,y);
		for (int i=0; i<4; i++)
		{
			int xx = x + dx[i];
			int yy = y + dy[i];
			while (checkbien(xx,yy) && vs[xx][yy] == -1 && map[xx][yy] == '0')
			{
					push(xx,yy);
					vs[xx][yy] = vs[x][y] +1;
					if (xx == ex && yy == ey) return;
					xx +=dx[i];
					yy +=dy[i];
			}
		}
	}
}



int main()
{
	freopen("input.txt","r",stdin);
	cin >> t;
	for (int tc =1; tc<=t; tc++)
	{
		cin >> n >> m ;
		cin >> sty >> stx >> ey >> ex;
		for (int i=1; i<=m; i++)
			for (int j=1; j<=n; j++) cin >> map[i][j];
		/*for (int i=1; i<=m; i++)
		{
			for (int j=1; j<=n; j++)
			{
				cout << map[i][j];
			}
			cout << endl;
		}*/
		Bfs();

		ans = vs[ex][ey]-1;
		if (ans ==-2 ) ans = -1;
		cout << ans << endl;

	}

}