Untitled
user_8149305
plain_text
a month ago
2.3 kB
0
Indexable
Never
///taiiii Crazyyy Kinggg #include <iostream> using namespace std; char map[505][505]; int n, m, start, last; int dx[] = { 1,-1,-2,-2,-1,1,2,2 }; int dy[] = { 2,2,1,-1,-2,-2,-1,1 }; int dxk[] = { -1,0,0,1,-1,1,1,-1 }; int dyk[] = { 0,1,-1,0,1,1,-1,-1 }; int cnt[505][505]; int visited[505][505]; int xStart, yStart, xTarget, yTarget; int xQueue[2000000]; int yQueue[2000000]; void BFSZ() { int xCur, yCur, xNext, yNext; while (start != last) { xCur = xQueue[start]; yCur = yQueue[start++]; visited[xCur][yCur] = 1; for (int i = 0; i < 8; i++) { xNext = xCur + dx[i]; yNext = yCur + dy[i]; if (xNext >= 0 && xNext < n && yNext >= 0 && yNext < m && visited[xNext][yNext] == 0 && map[xNext][yNext] != 'A' && map[xNext][yNext] != 'B') { visited[xNext][yNext] = 1; cnt[xNext][yNext] = -1; /*xQueue[last] = xNext; yQueue[last++] = yNext;*/ } } } } void BFSA() { start = 0; last = 0; xQueue[last] = xStart; yQueue[last++] = yStart; visited[xStart][yStart] = 1; int xCur, yCur; int xNext, yNext; while (start != last) { xCur = xQueue[start]; yCur = yQueue[start++]; for (int i = 0; i < 8; i++) { xNext = xCur + dxk[i]; yNext = yCur + dyk[i]; if (xNext >= 0 && xNext < n && yNext >= 0 && yNext < m && map[xNext][yNext] != 'Z') { if (visited[xNext][yNext] == 0 || cnt[xNext][yNext] > cnt[xCur][yCur] + 1) { cnt[xNext][yNext] = cnt[xCur][yCur] + 1; xQueue[last] = xNext; yQueue[last++] = yNext; visited[xNext][yNext] = 1; } if (map[xNext][yNext] == 'B') { return; } } } } } int main() { FILE* stream; freopen_s(&stream, "Text.txt", "r", stdin); int T; cin >> T; start = 0; last = 0; for (int tc = 1; tc <= T; tc++) { cin >> n >> m; for (int i = 0; i < n; i++) { cin >> map[i]; for (int j = 0; j < m; j++) { visited[i][j] = 0; cnt[i][j] = 0; if (map[i][j] == 'A') { xStart = i; yStart = j; } if (map[i][j] == 'B') { xTarget = i; yTarget = j; } if (map[i][j] == 'Z') { visited[i][j] = 1; cnt[i][j] = -1; xQueue[last] = i; yQueue[last++] = j; } } } BFSZ(); BFSA(); if (cnt[xTarget][yTarget] == 0) { cnt[xTarget][yTarget] = -1; } cout << cnt[xTarget][yTarget] << endl; } return 0; }
Leave a Comment