Untitled
user_8149305
plain_text
a month ago
1.8 kB
0
Indexable
Never
Battle City //tgt //test //doan code chua dung lam #include<iostream> using namespace std; char map[500][500]; int check[500][500]; int visited[500][500]; int x, y, t, z; int n, m; int start, last; int xCur, yCur, xNext, yNext; int xQueue[500]; int yQueue[500]; int dx[] = { 1,-1,0,0 }; int dy[] = { 0,0,1,-1 }; void BFS(int x, int y) { start = 0; last = 0; visited[x][y] = 1; check[x][y] = 0; xQueue[last] = x; yQueue[last++] = y; while (start != last) { xCur = xQueue[start]; yCur = yQueue[start++]; visited[xCur][yCur] = 1; for (int i = 0; i < 4; i++) { xNext = xCur + dx[i]; yNext = yCur + dy[i]; if (visited[xNext][yNext] == 0 && xNext >= 0 && xNext < n && yNext >= 0 && yNext < m && map[xNext][yNext] != 'S' && map[xNext][yNext] != 'R') { xQueue[last] = xNext; yQueue[last++] = yNext; if (map[xNext][yNext] == 'E' && (check[xNext][yNext] > check[xCur][yCur] + 1 || check[xNext][yNext] == 0)) { check[xNext][yNext] = check[xCur][yCur] + 1; } if (map[xNext][yNext] == 'B' && (check[xNext][yNext] > check[xCur][yCur] + 2 || check[xNext][yNext] == 0)) { check[xNext][yNext] = check[xCur][yCur] + 2; } if (map[xNext][yNext] == 'T' && (check[xNext][yNext] > check[xCur][yCur] + 1 || check[xNext][yNext] == 0)) { check[xNext][yNext] = check[xCur][yCur] + 1; } } } } } int main() { int T; cin >> T; 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++) { if (map[i][j] == 'Y') { x = i; y = j; } if (map[i][j] == 'T') { t = i; z = j; } visited[i][j] = 0; check[i][j] = 0; } } BFS(x, y); cout << "Case #" << tc << " " << check[t][z] << endl; } return 0; }
Leave a Comment