Untitled

 avatar
user_2087184
plain_text
3 months ago
2.5 kB
3
Indexable
Never
#include <iostream>
using namespace std;
const int SIZE = 100000;
int m, n, a[51][51], vt[51][51], sx, sy, ex, ey;

int rspinv[] = { -1, 1 };
int cspinh[] = { -1, 1 };

struct Point {
	int x, y;
};

template <typename T>
class Queue {
	int front, rear;
	T data[SIZE];
public:
	Queue() {
		front = rear = -1;
	}
	void reset() {
		front = rear = -1;
	}
	bool isEmpty() {
		return front == -1;
	}
	bool isFull() {
		return (front == 0 && rear == SIZE - 1) || (front == rear + 1);
	}
	void enQueue(T val) {
		if (!isFull()) {
			if (front == -1)	front++;
			rear = (rear + 1) % SIZE;
			data[rear] = val;
		}
	}
	T deQueue() {
		if (!isEmpty()) {
			T element = data[front];
			if (front == rear)	reset();
			else front = (front + 1) % SIZE;
			return element;
		}
	}
};

Queue<Point> q;

void solve(int index) {
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
			vt[i][j] = 0;
			if (a[i][j] == 2) {
				sx = i;
				sy = j;
			}
			else if (a[i][j] == 3) {
				ex = i;
				ey = j;
			}
		}
	}
	q.reset();
	Point start = { sx, sy };
	q.enQueue(start);
	vt[sx][sy] = 1;
	while (!q.isEmpty()) {
		Point c = q.deQueue();
		for (int i = 0; i < 2; i++) {
			int x = c.x;
			int y = c.y + cspinh[i];
			if (x >= 0 && y >= 0 && x < m && y < n && a[x][y] != 0 && (vt[x][y] == 0 || vt[x][y] > vt[c.x][c.y])) {
				Point next = { x, y };
				vt[x][y] = vt[c.x][c.y];
				if (x != ex || y != ey)
					q.enQueue(next);
			}
		}
		for (int i = 0; i < 2; i++) {
			int x = c.x + rspinv[i];
			int y = c.y;
			if (x >= 0 && y >= 0 && x < m && y < n) {
				if ((a[x][y] == 1 || a[x][y] == 3) && (vt[x][y] == 0 || vt[x][y] > vt[c.x][c.y])) {
					Point next = { x, y };
					vt[x][y] = vt[c.x][c.y];
					if (x != ex || y != ey)
						q.enQueue(next);
					continue;
				}
				if (a[x][y] == 0) {
					int bn = 1;
					while (a[x][y] == 0 && x >= 0 && x < m) {
						x = x + rspinv[i];
						bn++;
					}
					if ((a[x][y] == 1 || a[x][y] == 3) && (vt[x][y] == 0 || vt[x][y] > bn)) {
						Point next = { x, y };
						vt[x][y] = bn;
						if (x != ex || y != ey)
							q.enQueue(next);
					}
				}
			}
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cout << vt[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

int main() {
	int t;
	cin >> t;
	for (int i = 1; i <= t; i++) {
		solve(i);
	}
}
Leave a Comment