Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
2.4 kB
5
Indexable
Never
#include<iostream>
using namespace std;

int T, hang, cot, vtdx, vtdy, vtcx, vtcy;
char a;
int arr[205][205];
int visit[205][205];
int front = 0, rear = 0;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int rs, count1, s;

struct toado
{	int x;
	int y;
};
toado queu[10000000];

void init(){
	front = 0;
	rear = 0;
}

void push(int xx, int yy) {
	queu[rear].x = xx;
	queu[rear].y = yy;
	rear ++;
}

toado pop() {
	toado t = queu[front];
	front ++;
	return t;
}

void BFS(int x, int y) {
	init();
	push(x,y);
	visit[x][y] = 0;
	while (front < rear) {
		toado t = pop();
		s = visit[t.x][t.y];
		for(int i = t.y+1; i < cot; i ++) {
			if(arr[t.x][i] == 0){
				if(visit[t.x][i] == 0){
					push(t.x, i);
					visit[t.x][i] = s + 1;
				}
				else{
					if(s + 1 < visit[t.x][i]){
						push(t.x, i);
						visit[t.x][i] = s + 1;
					}
				}
			}
			else break;
		}

		for(int i = t.y-1; i >= 0; i --) {
			if(arr[t.x][i] == 0){
				if(visit[t.x][i] == 0){
					push(t.x, i);
					visit[t.x][i] = s + 1;
				}
				else{
					if(s + 1 < visit[t.x][i]){
						push(t.x, i);
						visit[t.x][i] = s + 1;
					}
				}
			}
			else break;
		}

		for(int i = t.x-1; i >= 0; i --) {
			if(arr[i][t.y] == 0){
				if(visit[i][t.y] == 0){
					push(i, t.y);
					visit[i][t.y] = s + 1;
				}
				else{
					if(s + 1 < visit[i][t.y]){
						push(i, t.y);
						visit[i][t.y] = s + 1;
					}
				}
			}
			else break;
		}

		for(int i = t.x+1; i < hang; i ++) {
			if(arr[i][t.y] == 0){
				if(visit[i][t.y] == 0){
					push(i, t.y);
					visit[i][t.y] = s + 1;
				}
				else{
					if(s + 1 < visit[i][t.y]){
						push(i, t.y);
						visit[i][t.y] = s + 1;
					}
				}
			}
			else break;
		}
	}
}

int main()
{
	freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin >> T;
	for(int test_case = 1; test_case <= T; test_case ++) {
		cin >> cot >> hang;
		cin >> vtdy >> vtdx >> vtcy >> vtcx;
		vtdy --; vtdx --; vtcy --; vtcx --;
		for(int i = 0; i < hang; i ++) {
			for(int j = 0; j < cot; j ++) {
				visit[i][j] = 0;
				cin >> a;
				if(a == '1') {
					arr[i][j] = 1;
				}
				else arr[i][j] = 0;
			}
		}
		s = 0;
		BFS(vtdx, vtdy);
		if(visit[vtcx][vtcy] == 0) cout << -1 << endl;
		else cout << visit[vtcx][vtcy] - 1<< endl;
	}
	return 0;
}