Untitled

 avatar
user_8149305
plain_text
a month ago
2.5 kB
0
Indexable
Never
////taiii
//code nop Fast robot
#include<iostream>
using namespace std;
char map[205][205];
int cnt[205][205];
int visited[205][205];
int N, M, xStart, yStart, xTarget, yTarget;
int start, last, xNext, yNext;
int xQueue[1000000];
int yQueue[1000000];
int dx[] = { 1,0,0,-1 };
int dy[] = { 0,1,-1,0 };


void BFS() {
	int xCur, yCur;
	start = 0;
	last = 0;
	xQueue[last] = xStart;
	yQueue[last++] = yStart;
	visited[xStart][yStart] = 1;
	while (start != last) {
		xCur = xQueue[start];
		yCur = yQueue[start++];
		for (int i = 0; i < 4; i++) {
			xNext = xCur + dx[i];
			yNext = yCur + dy[i];
			if (xNext >= 0 && xNext < M && yNext >= 0 && yNext < N && visited[xNext][yNext] == 0 && map[xNext][yNext] != '1') {

				if (dx[i] == 1) {
					int k = 0;
					while (xNext + k >= 0 && xNext + k < M && map[xNext + k][yNext] != '1') {
						cnt[xNext + k][yNext] = cnt[xCur][yCur] + 1;
						visited[xNext+k][yNext] = 1;
						xQueue[last] = xNext + k;
						yQueue[last++] = yNext;
						k += dx[i];
					}
				}
				if (dx[i] == -1) {
					int k = 0;
					while (xNext + k >= 0 && xNext + k < M && map[xNext + k][yNext] == '0') {
						cnt[xNext + k][yNext] = cnt[xCur][yCur] + 1;
						visited[xNext+k][yNext] = 1;
						xQueue[last] = xNext + k;
						yQueue[last++] = yNext;
						k += dx[i];
					}
				}
				if (dy[i] == 1) {
					int k = 0;
					while ((yNext + k >= 0 && yNext  + k < N) && map[xNext][yNext + k] != '1') {
						cnt[xNext][yNext + k] = cnt[xCur][yCur] + 1;
						xQueue[last] = xNext;
						yQueue[last++] = yNext + k;
						visited[xNext][yNext+k] = 1;
						k += dy[i];
					}
				}
				if (dy[i] == -1) {
					int k = 0;
					while (yNext + k >= 0 && yNext + k < M && map[xNext][yNext + k] != '1') {
						cnt[xNext][yNext + k] = cnt[xCur][yCur] + 1;
						visited[xNext][yNext + k] = 1;
						xQueue[last] = xNext;
						yQueue[last++] = yNext+k;
						k += dy[i];
					}
				}
				/*if (xNext == xTarget && yNext == yTarget) {
					return;
				}*/
				
			}
		}
	}
}

int main() {
	FILE *stream;
	freopen_s(&stream, "Text.txt", "r",stdin);
	int T;
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		cin >> N >> M;
		cin >> yStart >> xStart >> yTarget >> xTarget;
		for (int i = 0; i < M; i++) {
			cin >> map[i];
			for (int j = 0; j < N; j++) {
				visited[i][j] = 0;
				cnt[i][j] = 0;
			}
		}
		xStart--;
		yStart--;
		xTarget--;
		yTarget--;
		BFS();
		cout << cnt[xTarget][yTarget] - 1 << endl;
	}
	return 0;
}
Leave a Comment