crazykingsol

 avatar
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