Untitled
unknown
plain_text
5 months ago
1.5 kB
4
Indexable
Never
// In Practice, You should use the statndard input/output // in order to receive a score properly. // Do not use file input and output. Please be very careful. #include<iostream> using namespace std; int N, M; int sx,sy,ex,ey; char arr[210][210]; int vis[210][210]; int Qx[100000]; int Qy[100000]; int front, rear; int dy[4]={-1,1,0,0}; int dx[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; if(xx==ex && yy==ey) { return; } push(xx,yy); xx+=dx[i]; yy+=dy[i]; } } } } int main() { int test_case; int T; //freopen("input.txt", "r", stdin); cin >> T; for(test_case = 1; test_case <= T; ++test_case) { //for (int i=1;i<=209;i++) { // for (int j=1;j<=209;j++) { // arr[i][j]='0'; // vis[i][j]=1000; // } //} 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; }