Untitled
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