Untitled
unknown
plain_text
2 years ago
1.5 kB
14
Indexable
// 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;
}Editor is loading...