Untitled

mail@pastecode.io avatar
unknown
plain_text
17 days ago
2.1 kB
2
Indexable
Never
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;

#define MAXQUEUE 25000

class Queue
{
public:
	int head, rear;
	int A[MAXQUEUE];
	Queue();
	void enQueue(int inS);
	int deQueue();
	bool is_Empty();
	void reset();

private:

};

Queue::Queue()
{
	head = rear = -1;
}

void Queue::enQueue(int inS) {
	A[++rear] = inS;
}

int Queue::deQueue() {
	return A[++head];
}

bool Queue::is_Empty() {
	return head == rear;
}

void Queue::reset() {
	head = rear = -1;
}

int nTestcase, N, M, rStart, cStart, rEnd, cEnd, rr, cc, nr, nc, Min;
int Map[50][50];
bool visited[50][50];
int rspin[4] = { -1,1,0,0 };
int cspin[4] = { 0,0,-1,1 };
Queue rQueue, cQueue;

void resetVisit() {
	for (int i = 0; i <= rQueue.rear; i++) {
		visited[rQueue.A[i]][cQueue.A[i]] = false;
	}
}

bool BFS(int colMax) {
	resetVisit();
	visited[rStart][cStart] = true;
	rQueue.reset();
	cQueue.reset();
	rQueue.enQueue(rStart);
	cQueue.enQueue(cStart);
	while (rQueue.is_Empty() == false) {
		rr = rQueue.deQueue();
		cc = cQueue.deQueue();
		for (int i = 0; i < 4; i++) {
			for (int j = 1; j <= colMax; j++) {
				nr = rr + rspin[i]*j;
				nc = cc + cspin[i];
				if (nr >= 0 && nr < N && nc >= 0 && nc < M && visited[nr][nc] == false && Map[nr][nc] != 0) {
					if (nr == rEnd && nc == cEnd) {
						return true;
					}
					visited[nr][nc] = true;
					rQueue.enQueue(nr);
					cQueue.enQueue(nc);
				}
			}
		}
	}
	return false;
}

int main() {
	freopen("input.txt", "r", stdin);
	cin >> nTestcase;
	for (int testcase = 1; testcase <= nTestcase; testcase++) {
		cin >> N >> M;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				cin >> Map[i][j];
				if (Map[i][j] == 2) {
					rStart = i;
					cStart = j;
				}
				else if (Map[i][j] == 3) {
					rEnd = i;
					cEnd = j;
				}
			}
		}
		Min = -1;
		for (int i = 1; i <= N; i++) {
			bool check = BFS(i);
			if (check) {
				Min = i;
				break;
			}
		}
		cout << "Case #" << testcase << endl << Min << endl;
	}
	return 0;
}
Leave a Comment