Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.3 kB
1
Indexable
Never
#include<iostream>
using namespace std;
int M, N, SR, SC, ER, EC;
int Qx[10000], Qy[10000];
int f = -1, r =-1;
char a[200][200];
int visited[200][200];
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};

void pop(int &x, int &y) { 
	r++;
	x = Qx[r];
	y = Qy[r];
}

void push(int x, int y) { 
	f++;
	Qx[f] = x;
	Qy[f] = y;
}

void bfs(int sx, int sy) { 
	f = r = -1;
	push(sx, sy);
	visited[sx][sy] = 0;
	int x = 0, y = 0;
	while (r != f) {
		pop(x, y);
		for(int i = 0; i < 4; i++) { 
			int xx = x + dx[i];
			int yy = y + dy[i];

			while (xx >= 1 && xx <= M && yy >=1 && yy <= N && a[xx][yy] == '0' && visited[xx][yy] ==0) {
				push(xx, yy);
				visited[xx][yy] = visited[x][y] + 1;
				if(xx == ER && yy == EC) { 
					return;
				}
				xx += dx[i];
				yy += dy[i];
			}
		}
	}
}

void reset() {
	for(int  i = 1; i <= M; i++) { 
		for(int j = 1; j <= N; j++) { 
			visited[i][j] = 0;
		}
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	int T;
	cin>>T;
	for(int tc = 1; tc <= T; tc++) { 
		cin>>N>>M;
		reset();
		cin>>SC>>SR>>EC>>ER;
		for(int  i = 1; i <= M; i++) { 
			for(int j = 1; j <= N; j++) { 
				cin>>a[i][j];
			}
		}
		bfs(SR, SC);
		cout<<visited[ER][EC] - 1<<endl;
	}
	return 0;
}