Untitled
unknown
plain_text
2 years ago
1.3 kB
4
Indexable
#include<iostream> using namespace std; int N, M; int sx,sy,ex,ey; char arr[210][210]; int vis[210][210]; int Qx[10000000]; int Qy[10000000]; int front, rear; int dx[4]={-1,1,0,0}; int dy[4]={0,0,1,-1}; void push(int x, int y) { rear++; Qx[rear]=x; Qy[rear]=y; } void pop(int &x, int &y) { front++; x=Qx[front]; y=Qy[front]; } void bfs(int x, int y) { front=rear= -1; push(x,y); vis[x][y]=0; while (front != rear) { pop(x,y); for (int i=0;i<4;i++) { int xx=x+dx[i]; int yy=y+dy[i]; while (xx>=1 && xx<=N && yy>=1 && yy<=M && arr[xx][yy]=='0' && (vis[xx][yy] == -1 || vis[xx][yy] >=vis[x][y]+1) ) { vis[xx][yy] = vis[x][y] + 1; if(xx==ex && yy==ey) { return; } push(xx,yy); xx+=dx[i]; yy+=dy[i]; } } } } int main() { int test_case; int T; freopen("input1.txt", "r", stdin); cin >> T; for(test_case = 1; test_case <= T; ++test_case) { cin >> M >> N; cin >> sy >> sx; cin >> ey >> ex; for (int i=1;i<=N;i++) { for (int j=1;j<=M;j++) { cin >> arr[i][j]; vis[i][j] = -1; } } bfs(sx,sy); if(vis[ex][ey]==-1) { cout << -1 << endl; } else { cout << vis[ex][ey]-1 << endl; } } return 0; }
Editor is loading...