Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.9 kB
1
Indexable
Never
#include<iostream>
using namespace std;
#define max 100000

int n, m, p, q, s, t;
int map[200][200];
int quanCo[200][2];
int dx[]={-1,-1,1,1};
int dy[]={-1,1,-1,1};
int front,rear;
int visit[200][200];
int qx[max];
int qy[max];
int ans;


void push(int x, int y){
	rear++;
	qx[rear]=x;
	qy[rear]=y;
}

void pop(){
	front++;
}

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


void reset(){
	for(int i =1;i<=n;i++){
		for(int j =1;j<=n;j++){
			map[i][j]=0;
		}
	}
}

void resetVisit(){
	front= rear=-1;
	for(int i =1;i<=n;i++){
		for(int j=1;j<=n;j++){
			visit[i][j]=999;
		}
	}
}

void in(){
	for(int i =1;i<=n;i++){
		for(int j =1;j<=n;j++){
			cout<<map[i][j];
		}
		cout<<endl;
	}
}

void inVisit(){
	for(int i =1;i<=n;i++){
		for(int j =1;j<=n;j++){
			cout<<visit[i][j]<<" ";
		}
		cout<<endl;
	}
}


void bfs(int x,int y){
	visit[x][y]=0;
	inVisit();
	push(x,y);
	while(!isEmpty()){
		pop();
		int xtop = qx[front];
		int ytop = qy[front];
		for(int i=0;i<4;i++){
			int xtemp = xtop+dx[i];
			int ytemp = ytop+dy[i];
			if(xtemp>0&&ytemp>0&&xtemp<=n&&ytemp<=n&&visit[xtemp][ytemp]>visit[xtop][ytop]+1&&map[xtemp][ytemp]!=1){
				visit[xtemp][ytemp]=visit[xtop][ytop]+1;
				inVisit();
				while(xtemp>0&&ytemp>0&&xtemp<=n&&ytemp<=n&&visit[xtemp][ytemp]>visit[xtop][ytop]+1&&map[xtemp][ytemp]!=1){
					int r = xtemp+dx[i];
					int c = ytemp+dy[i];
					inVisit();
					push(xtemp,ytemp);
				}
				
			}
        
		}

	}
}



int main(){
	freopen("quantuong.txt", "r", stdin);
	int T; cin >> T;
	for(int tc = 1; tc <= T;tc++){
		reset();
		resetVisit();
		inVisit();
		cin >> n >> m >> p>>q>>s>>t;
		for(int i  = 0; i < m; i++){
			cin>>quanCo[i][0]>>quanCo[i][1];
			map[quanCo[i][0]][quanCo[i][1]]=1;
		}
		map[p][q]=2;
		map[s][t]=3;
		//in();
		bfs(p,q);
		cout<<visit[s][t]<<endl;
	}	

	return 0;
}