Untitled
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