Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.2 kB
5
Indexable
Never
#include <iostream>
#define MAXN 201
#define MAXQ 200000
	
using namespace std;

int N, M;
int xStart, yStart, xEnd, yEnd;
char map[MAXN][MAXN];
int visit[MAXN][MAXN];
int Q[MAXQ];
int front, rear;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int ans;

void push(int x, int y)
{
	rear++;
	Q[rear%MAXQ] = x;
	rear++;
	Q[rear%MAXQ] = y;
}

int pop()
{
	front++;
	return Q[front%MAXQ];
}

void resetQ()
{
	front = -1;
	rear = -1;
}

void input()
{
	cin >> N >> M;
	cin >> yStart >> xStart >> yEnd >> xEnd;
	for(int i = 1; i <= M;i++){
		for(int j = 1; j <= N; j++){
			cin >> map[i][j];
			visit[i][j] = -1;
			
		}
	}
}

void BFS()
{
	resetQ();
	push(xStart, yStart);
	visit[xStart][yStart] = 0;
	
	while(front != rear){
		int xCur = pop();
		int yCur = pop();
		
		for(int i = 0; i < 4; i++){
			int xNext = xCur + dx[i];
			int yNext = yCur + dy[i];
			if(xNext < 1 || yNext < 1 || xNext > M || yNext > N )
				continue;
			while(map[xNext][yNext] == '0' && (visit[xNext][yNext] == -1 || visit[xNext][yNext] >= visit[xCur][yCur] + 1)){
				visit[xNext][yNext] = visit[xCur][yCur] +1;
				if(xNext == xEnd && yNext == yEnd)
					return;
				push(xNext, yNext);
				xNext = xNext + dx[i];
				yNext = yNext + dy[i];
			}

			/*while (xNext >= 1 && yNext >= 1 && xNext <= M && yNext <= N && map[xNext][yNext] == '0') { 
				if (visit[xNext][yNext] == -1 || visit[xNext][yNext] >= (visit[xCur][yCur] + 1)) { 
					visit[xNext][yNext] = visit[xCur][yCur] + 1; 
					if (xNext == xEnd && yNext == yEnd) 
						return; 
					push(xNext, yNext); 
					xNext = xNext + dx[i]; 
					yNext = yNext + dy[i]; 
				} 
				else 
					break; 
			}*/
		}
	}
}

int main()
{
	freopen("input.txt", "r", stdin);
	int T;
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		input();
		ans = 0;
		BFS();
		if(visit[xEnd][yEnd] != -1)
			cout << visit[xEnd][yEnd] - 1<< endl;
		else
			cout << "-1" << endl;
	}
	return 0;


}


3
7 7
1 2 7 5
1111111
0000000
1011000
1011100
1011110
1000000
1111111
7 7
1 2 7 5
1111111
0000011
1011001
1011100
1011110
1000000
1111111
7 7
1 2 7 6
1111111
0000001
1011000
1011100
1011110
1000000
1111111