Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.3 kB
1
Indexable
Never
#include<iostream>

using namespace std;
int N, M;
int sx,sy,ex,ey;
char arr[210][210];
int vis[210][210];
int Qx[10000000];
int Qy[10000000];
int front, rear;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,1,-1};

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(int x, int y) {
	front=rear= -1;
	push(x,y);
	vis[x][y]=0;
	while (front != rear) {
		pop(x,y);
		for (int i=0;i<4;i++) {
			int xx=x+dx[i];
			int yy=y+dy[i];
			while (xx>=1 && xx<=N && yy>=1 && yy<=M && arr[xx][yy]=='0' && (vis[xx][yy] == -1 || vis[xx][yy] >=vis[x][y]+1) ) {
				vis[xx][yy] = vis[x][y] + 1;
				if(xx==ex && yy==ey) {
					return;
				}
				push(xx,yy);
				xx+=dx[i];
				yy+=dy[i];
			}
		}
	}
}
int main()
{
	int test_case;
	int T;
	freopen("input1.txt", "r", stdin);
	cin >> T;

	for(test_case = 1; test_case <= T; ++test_case)
	{
		cin >> M >> N;
		cin >> sy >> sx;
		cin >> ey >> ex;
		for (int i=1;i<=N;i++) {
			for (int j=1;j<=M;j++) {
				cin >> arr[i][j];
				vis[i][j] = -1;
			}
		}
		bfs(sx,sy);
		if(vis[ex][ey]==-1) {
			cout << -1 << endl;
		} else {
			cout << vis[ex][ey]-1 << endl;
		}
		
	}
	return 0;
}