Untitled
user_8149305
plain_text
a year ago
2.5 kB
9
Indexable
////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;
}Editor is loading...
Leave a Comment