Untitled

 avatar
unknown
plain_text
2 years ago
1.7 kB
5
Indexable
// 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 ,p,q, s,t;
#define size 10000000
int queue[size];
int front =-1;
int rear=-1;
int map[205][205];
int dx[4]={-1,-1,1,1};
int dy[4]={-1,1,-1,1};
int visit[205][205];
int ans;

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 reset(){
	for(int i=0 ; i<205; i++){
		for( int j=0 ; j< 205 ; j++){
			map[i][j]=0;
			visit[i][j]=-1;
		}

	}

}
void bfs( int x, int y){
	front=rear=-1;
	push(x);
	push(y);
	visit[x][y] = 0;

	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];
			while(x2 >= 1 && x2 <= n && y2 <= n && y2 >= 1 && map[x2][y2] == 0)
			{
				
				if( visit[x2][y2] == -1)
				{
					visit[x2][y2]= visit[x1][y1] + 1;
					push(x2);
					push(y2);
				}
				if( x2== s && y2 ==t) return ;
				x2+=dx[i];
				y2+=dy[i];
			}
		}

	}
}




int main(int argc, char** argv)
{
	int test_case;
	int T;


	//freopen("text.txt", "r", stdin);
	cin >> T;

	/*
	Read each test case from standard input.
	*/
	for(test_case = 1; test_case <= T; ++test_case)
	{
		ans = -1;
		reset();
		cin>>n>>m>>p>>q>>s>>t;
		for(int i=0 ; i<m; i++){
			int a,b;
			cin>>a>>b;
			map[a][b]=1;
		}
		
		bfs(p,q);
		cout  << visit[s][t] << endl;
	}
	return 0;//Your program should return 0 on normal termination.
}
Editor is loading...