Untitled
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. }