Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.4 kB
2
Indexable
Never
#include<iostream>

using namespace std;
int a[1000][1000], vis[1000][1000];
int m,n, fr, er,dem;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
//1 di len //  2 di xuong// 3 sang trai// 4 sang phai
struct Queue{
	int x;
	int y;
};
Queue queue[10000000];
void enQueue(int xx, int yy){
	queue[er].x = xx;
	queue[er].y = yy;
	er++;
}
Queue deQueue(){
	Queue t = queue[fr];
	fr++;
	return t;
}
//lenxuong
void BFS(int x, int y){
	vis[x][y]=0;
	enQueue(x,y);
	while(er!=fr){
		Queue vitri = deQueue();
		int xc=vitri.x;
		int yc=vitri.y;
		for(int i=0;i<4;i++){
				int xi = xc + dx[i];
				int yi = yc + dy[i];
				while(xi > 0 && xi <= n && yi > 0 && yi <= m && a[xi][yi] != 1 && (vis[xi][yi] == 0 || vis[xi][yi] >= vis[xc][yc] + 1)){
					enQueue(xi,yi);	
					vis[xi][yi] = vis[xc][yc] + 1;
					xi = xi + dx[i];
					yi = yi + dy[i];	
			}
		}
	}
}
int main(int argc, char** argv)
{
	int test_case;
	int T;
	ios::sync_with_stdio(false);
	freopen("input.txt", "r", stdin);
	cin >> T;
	for(test_case = 1; test_case <= T; ++test_case)
	{
		dem=-1;
		cin >> m >> n;
		int xbd, ybd ,xkt,ykt ;
		cin >> ybd >> xbd >> ykt >> xkt;
		char s;
		for(int i = 1; i <= n;i++){
			for(int j =1; j<=m;j++){
				cin >> s;
				a[i][j]=s-48;
				vis[i][j]=0;
			}
		}

		BFS(xbd,ybd);
		
		cout <<vis[xkt][ykt]-1<< endl;
	}
	return 0;//Your program should return 0 on normal termination.
}