Untitled
plain_text
a month ago
2.4 kB
5
Indexable
Never
#include<iostream> using namespace std; int T, hang, cot, vtdx, vtdy, vtcx, vtcy; char a; int arr[205][205]; int visit[205][205]; int front = 0, rear = 0; int dx[] = {-1, 0, 1, 0}; int dy[] = {0, 1, 0, -1}; int rs, count1, s; struct toado { int x; int y; }; toado queu[10000000]; void init(){ front = 0; rear = 0; } void push(int xx, int yy) { queu[rear].x = xx; queu[rear].y = yy; rear ++; } toado pop() { toado t = queu[front]; front ++; return t; } void BFS(int x, int y) { init(); push(x,y); visit[x][y] = 0; while (front < rear) { toado t = pop(); s = visit[t.x][t.y]; for(int i = t.y+1; i < cot; i ++) { if(arr[t.x][i] == 0){ if(visit[t.x][i] == 0){ push(t.x, i); visit[t.x][i] = s + 1; } else{ if(s + 1 < visit[t.x][i]){ push(t.x, i); visit[t.x][i] = s + 1; } } } else break; } for(int i = t.y-1; i >= 0; i --) { if(arr[t.x][i] == 0){ if(visit[t.x][i] == 0){ push(t.x, i); visit[t.x][i] = s + 1; } else{ if(s + 1 < visit[t.x][i]){ push(t.x, i); visit[t.x][i] = s + 1; } } } else break; } for(int i = t.x-1; i >= 0; i --) { if(arr[i][t.y] == 0){ if(visit[i][t.y] == 0){ push(i, t.y); visit[i][t.y] = s + 1; } else{ if(s + 1 < visit[i][t.y]){ push(i, t.y); visit[i][t.y] = s + 1; } } } else break; } for(int i = t.x+1; i < hang; i ++) { if(arr[i][t.y] == 0){ if(visit[i][t.y] == 0){ push(i, t.y); visit[i][t.y] = s + 1; } else{ if(s + 1 < visit[i][t.y]){ push(i, t.y); visit[i][t.y] = s + 1; } } } else break; } } } int main() { freopen("input.txt", "r", stdin); ios::sync_with_stdio(false); cin >> T; for(int test_case = 1; test_case <= T; test_case ++) { cin >> cot >> hang; cin >> vtdy >> vtdx >> vtcy >> vtcx; vtdy --; vtdx --; vtcy --; vtcx --; for(int i = 0; i < hang; i ++) { for(int j = 0; j < cot; j ++) { visit[i][j] = 0; cin >> a; if(a == '1') { arr[i][j] = 1; } else arr[i][j] = 0; } } s = 0; BFS(vtdx, vtdy); if(visit[vtcx][vtcy] == 0) cout << -1 << endl; else cout << visit[vtcx][vtcy] - 1<< endl; } return 0; }