crazykingsol
quoc14
c_cpp
a month ago
2.6 kB
2
Indexable
Never
caidat
#include <iostream> using namespace std; // vua int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1}; int dy[8] = {0, 0, 1, -1, 1, -1, -1, 1}; //ma int dxx[8] = { -1, -2, -2, -1, 1, 2, 2, 1}; int dyy[8] = { -2, -1, 1, 2, 2, 1, -1, -2}; char a[400][400]; int dist[400][400]; int n, m; int queueX[1000005], queueY[1000005]; int x_start, y_start, x_end, y_end; int start, last; void reset() { for (int i = 0; i < 400; i++) { for (int j = 0; j < 400; j++) { dist[i][j] = 0; } } } void dima(int x, int y) { int x_next, y_next; for (int i = 0; i < 8; i++) { x_next = x + dxx[i]; y_next = y + dyy[i]; if (x_next >= 1 && x_next <= n && y_next >= 1 && y_next <= m && a[x_next][y_next] != 'Z') { a[x_next][y_next] = 'O'; } } } void bfs() { reset(); start = 0; last = 0; int x_cur, y_cur, x_next, y_next; queueX[last] = x_start; queueY[last++] = y_start; dist[x_start][y_start] = 1; while (start != last) { x_cur = queueX[start]; y_cur = queueY[start++]; for (int i = 0; i < 8; i++) { x_next = x_cur + dx[i]; y_next = y_cur + dy[i]; if (x_next >= 1 && x_next <= n && y_next >= 1 && y_next <= m) { if (a[x_next][y_next] == '.') { if (dist[x_next][y_next] == 0 || dist[x_next][y_next] > dist[x_cur][y_cur] + 1) { dist[x_next][y_next] = dist[x_cur][y_cur] + 1; queueX[last] = x_next; queueY[last++] = y_next; } } if (a[x_next][y_next] == 'B') { if (dist[x_next][y_next] == 0 || dist[x_next][y_next] > dist[x_cur][y_cur] + 1) { dist[x_next][y_next] = dist[x_cur][y_cur] + 1; } } } } } } void solve(int testcase) { //cin >> n >> m; cin >> m >> n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; if (a[i][j] == 'A') { x_start = i; y_start = j; } if (a[i][j] == 'B') { x_end = i; y_end = j; } } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (a[i][j] == 'Z') { dima(i, j); } } } bfs(); /* for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cout << dist[i][j] << " "; } cout << endl; } */ // de mang dist la 0 neu ko di duoc - ans di 1 la xong int ans = dist[x_end][y_end]; //cout << "Case #" << testcase << endl; cout << ans - 1<< endl; } int main() { freopen("Text.txt", "r", stdin); int t; cin >> t; for (int i = 1; i <= t; i++) { solve(i); } }
Leave a Comment