Untitled
unknown
plain_text
a year ago
1.9 kB
3
Indexable
Never
#include<iostream> #define max 1000000 using namespace std; char a[305][305]; int visit[305][305]; int n,m; int cotS, hangS, cotE, hangE; int front= -1; int rear=-1; int queuex[1000000]; int queuey[1000000]; int luu_vt[1000][1000]; int luu_buoc[1000][1000]; int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0, -1, 0}; int ans,dem; void push(int x, int y){ if(rear == max-1) rear =-1; rear++; queuex[rear]=x; queuey[rear]=y; } void pop(){ if(front == max-1) front =-1; front++; } bool IsEmpty(){ return front == rear; } bool check(int i, int j){ if(i>=1 && i <=m && j >=1 && j <=n){ return true; } return false; } void Try(int hang, int cot){ front =rear =-1; push(hang, cot); luu_buoc[hang ][cot] = -1; luu_vt[hangS][cotS] = -1; while(!IsEmpty()){ pop(); int x1= queuex[front]; int y1= queuey[front]; for(int i=0; i<4; i++){ int x2= x1+dx[i]; int y2= y1 +dy[i]; if( check(x2, y2) ==true && a[x2][y2] == '0' && 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,y2); } } } } int main(){ freopen("Text.txt", "r", stdin); int test; cin >> test; for(int tc= 1; tc <= test; tc++){ cin >> n >> m; // n la cot, m la hang cin >> cotS >> hangS >> cotE >> hangE; for(int i=1; i<=m; i++){ for(int j =1; j<=n ; j++){ cin >> a[i][j]; } } for(int i=1; i<=m; i++){ for(int j=1; j<=n; j++){ luu_buoc[i][j] = 1000000; luu_vt[i][j]=-1; } } Try(hangS, cotS); if(luu_buoc[hangE][cotE] == 1000000) cout << -1 << endl; else cout << luu_buoc[hangE][cotE] << endl; } return 0; }