Untitled

mail@pastecode.io avatar
unknown
plain_text
17 days ago
1.9 kB
2
Indexable
Never
#include<iostream>
using namespace std;
int T, N, M, visited[1001][1001];
char a[1001][1001];
int hr[8] = { -1,-2,-2,-1,1,2,2,1 };
int hc[8] = { -2,-1,1,2,2,1,-1,-2 };
int kr[8] = {0,-1,-1,-1,0,1,1,1};
int kc[8] = {-1,-1,0,1,1,1,0,-1};
int x, y;
int rx, ry;
const int MAX = 10000;
struct Queue
{
	int queue[MAX];
	int front;
	int rear;
	void reset() {
		front = -1;
		rear = -1;
	}
	Queue() {
		reset();
	}
	void push(int value) {
		queue[++rear] = value;
	}
	int pop() {
		return queue[++front];
	}
	bool isEmpty() {
		return front == rear;
	}
};
void loang(int r,int c) {
	visited[r][c] = 1;
	for (int i = 0; i < 8; i++) {
		int _r = r + hr[i];
		int _c = c + hc[i];
		if (_r >= 0 && _c >= 0 && _r < N && _c < M &&a[_r][_c]!='A'&&a[_r][_c]!='B') {
			visited[_r][_c] = 1;
		}
	}
}

void bds(int x,int y) {
	Queue q;
	q.push(x);
	q.push(y);
	visited[x][y] = 1;
	while (!q.isEmpty())
	{
		int r = q.pop();
		int c = q.pop();
		for (int i = 0; i < 8; i++) {
			int _r = r + kr[i];
			int _c = c + kc[i];
			if (_r >= 0 && _c >= 0 && _r < N && _c < M&&!visited[_r][_c]&&a[_r][_c]!='*') {
				visited[_r][_c] = visited[r][c] + 1;
				q.push(_r);
				q.push(_c);
			}
		}
	}
}
int main() {
	//freopen("input.txt", "r", stdin);
	cin >> T;
	for (int t = 1; t <= T; t++) {
		cin >> N >> M;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				cin >> a[i][j];
				if (a[i][j] == 'A') {
					x = i;
					y = j;
				}
				
				if (a[i][j] == 'B') {
					rx = i;
					ry = j;
				}
				visited[i][j] = 0;
			}
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (a[i][j] == 'Z') {
					loang(i, j);
				}
			}
		}
		bds(x, y);
		if (visited[rx][ry] != 0) {
			cout << visited[rx][ry] - 1 << endl;
		}
		else cout << -1 << endl;
	}

	return 0;
}
Leave a Comment