Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.9 kB
3
Indexable
Never
#include<iostream>
#define max 1000000
using namespace std;
char a[305][305];
int visit[305][305];
int n,m;
int cotS, hangS, cotE, hangE;
int front= -1;
int	rear=-1;
int queuex[1000000];
int queuey[1000000];
int luu_vt[1000][1000];
int luu_buoc[1000][1000];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int ans,dem;
void push(int x, int y){
	if(rear == max-1) rear =-1;
	rear++;
	queuex[rear]=x;
	queuey[rear]=y;
}

void pop(){
	if(front == max-1) front =-1;
	front++;
}

bool IsEmpty(){
	return front == rear;
}

bool check(int i, int j){
	if(i>=1 && i <=m && j >=1 && j <=n){
		return true;
	}
	return false;
}

void Try(int hang, int cot){
	front =rear =-1;
	push(hang, cot);
	luu_buoc[hang ][cot] = -1;
	luu_vt[hangS][cotS] = -1;
	while(!IsEmpty()){
		pop();
		int x1= queuex[front];
		int y1= queuey[front];

		for(int i=0; i<4; i++){
			int x2= x1+dx[i];
			int y2= y1 +dy[i];
			if( check(x2, y2) ==true && a[x2][y2] == '0' && luu_buoc[x1][y1] < luu_buoc[x2][y2] ){
				luu_vt[x2][y2] = i;
				if( luu_vt[x2][y2]==luu_vt[x1][y1]){
					luu_buoc[x2][y2]=luu_buoc[x1][y1];
				}
				else if( luu_vt[x2][y2] != luu_vt[x1][y1]){
					luu_buoc[x2][y2] = luu_buoc[x1][y1]+1;
				}
				push(x2,y2);
				
			}
		}
	}

}
int main(){
	freopen("Text.txt", "r", stdin);
	int test;
	cin >> test;
	
	for(int tc= 1; tc <= test; tc++){
		cin >> n >> m; // n la cot, m la hang

		cin >> cotS >> hangS >> cotE >> hangE;

		for(int i=1; i<=m; i++){
			for(int j =1; j<=n ; j++){
				cin >> a[i][j];
			}
		}
		for(int i=1; i<=m; i++){
			for(int j=1; j<=n; j++){
				luu_buoc[i][j] = 1000000;
				luu_vt[i][j]=-1;
			}
		}
		
		Try(hangS, cotS);
		if(luu_buoc[hangE][cotE] == 1000000) cout << -1 << endl;
		else cout << luu_buoc[hangE][cotE] << endl;
	}
	return 0;
}