Untitled

 avatar
unknown
plain_text
a year ago
2.5 kB
7
Indexable
#include<iostream>
using namespace std;
char mang[100][100];
bool vt[100][100];
int dis[100][100];

const int maxn = 10000;

int dx[] = {0, 1, 1, 2, 2, -1, -1, -2, -2};
int dy[] = {0, 2, -2, 1, -1, 2, -2, 1, -1};

int cx[] = {0,0,1,-1,-1,-1,1,1};
int cy[] = {1,-1,0,0,-1,1,-1,1};

int t, n, m;

struct point {
	int x, y;
};

class Queue{
private:
	point arr[maxn];
	int front, rear;
public:
	Queue() {
		front = rear = -1;
	}

	bool isFull() {
		if (rear == maxn - 1) return true;
		return false;
	}

	bool isEmpty() {
		if (rear == front) return true;
		return false;
	}

	void enQueue(point val) {
		if (!isFull()) {
			rear++;
			arr[rear].x = val.x;
			arr[rear].y = val.y;
		}
	}

	point deQueue() {
		point s;
		if (!isEmpty()) {
			front++;
			s.x=arr[front].x;
			s.y=arr[front].y;
		}
		return s;
	}

	void reset() {
		front = rear = -1;
	}
};

Queue myQueue;
point p,st,en;

void bfs(point start, point end) {
	myQueue.reset();
	myQueue.enQueue(start);
	while (!myQueue.isEmpty()) {
		p = myQueue.deQueue();
		for (int i = 0; i < 8; i++) {
			int a = p.x + cx[i];
			int b = p.y + cy[i];
			if (a >= 0 && b >= 0 && a < n && b < m && vt[a][b] == true) {
				dis[a][b] = dis[p.x][p.y] + 1;
				vt[a][b] = false;
				point poi = {a,b};
				myQueue.enQueue(poi);
			}
			if (a == end.x && b == end.y)
				return;
		}
	}
}

void mark() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (mang[i][j] == 'Z') {
				for (int k = 0; k < 9; k++) {
					int nextMovex = i + dx[k];
					int nextMovey = j + dy[k];
					if (nextMovex >= 0 && nextMovey >= 0 && nextMovex < n && nextMovey < m )
						vt[nextMovex][nextMovey] = false;
				}
			}
		}
	}
	vt[en.x][en.y] = true;
}

void clear() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			vt[i][j] = true;
			dis[i][j] = 0;
		}
	}
}

void nhap() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> mang[i][j];
			if (mang[i][j] == 'A') {
				st.x = i;
				st.y = j;
			}
			if (mang[i][j] == 'B') {
				en.x = i;
				en.y = j;
			}
		}
	}
}

int main() {
	cin >> t;
	for (int tc = 1; tc <= t; tc++) {
		nhap();
		clear();
		mark();
		bfs(st,en);
		cout << "Case #" << tc << " ";
		if (dis[en.x][en.y] == 0) cout << "never" << endl;
		else cout << dis[en.x][en.y] << endl;
	}
	return 0;
}
Editor is loading...
Leave a Comment