Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.0 kB
1
Indexable
Never
// In Practice, You should use the statndard input/output
// in order to receive a score properly.
// Do not use file input and output. Please be very careful. 

#include<iostream>

using namespace std;
int N, M;
char arr[1000][1000];
int map[1000][1000];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int xbatdau, ybatdau, xdich, ydich;
int luu_vt[1000][1000];
int luu_buoc[1000][1000];
int const size =100000;
int queue[size];
int front=-1;
int rear=-1;
bool isEmpty(){
	return front==rear;
}
void push(int x){
	if(rear==size-1) rear=-1;
	rear++;
	queue[rear]=x;
}
int pop(){
	if(front ==size-1) front=-1;
	front++;
	return queue[front];
}
void bfs(int x, int y){
	front=rear=-1;
	push(x);
	push(y);
	luu_buoc[x][y] = -1;
	luu_vt[xbatdau][ybatdau] = -1;
	while(!isEmpty()){
		int x1=pop();
		int y1=pop();
		for(int i=0; i<4; i++){
			int x2= x1+dx[i];
			int y2= y1 +dy[i];
			if( x2 >= 1 && x2 <= N && y2>=1 && y2<=M && map[x2][y2] != 1 && 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);
				push(y2);
			}

		}

	}

}



void nhap(){
	for(int i=1; i<=N; i++){
		for(int j=1; j<=M; j++){
			cin>>arr[i][j];
			luu_buoc[i][j]=10000000;
			luu_vt[i][j]=-1;
			if(arr[i][j]=='1'){
				map[i][j]=1;
			}
			if(arr[i][j]=='0'){
				map[i][j]=0;
			}


		}

	}

}

int main(int argc, char** argv)
{
	int test_case;
	int T;
	//int Answer;
	freopen("text.txt", "r", stdin);
	cin >> T;
	for(test_case = 1; test_case <= T; ++test_case)
	{
		cin>>M>>N;
		cin>>ybatdau>>xbatdau>>ydich>>xdich;
		nhap();
		bfs(xbatdau, ybatdau);
		if(luu_buoc[xdich][ydich]==1000000){
			cout<<-1<<endl;
		}else cout<<luu_buoc[xdich][ydich]<<endl;
	}
	return 0;//Your program should return 0 on normal termination.
}