Untitled
unknown
plain_text
14 days ago
1.8 kB
0
Indexable
Never
#include <iostream> int T, N, M; int Mx, My; int Gx, Gy; int arr[60][60]; int visited[60][60]; using namespace std; class Queue{ int front, rear; int q[100000]; public: Queue(); void enQueue(int value); int deQueue(); void reset(); bool is_Empty(); }; Queue::Queue(){ front = rear = -1; } void Queue::enQueue(int value){ q[++rear] = value; } int Queue::deQueue(){ return q[++front]; } void Queue::reset(){ front = rear = -1; } bool Queue::is_Empty(){ return front == rear; } Queue rQueue, cQueue; int X[4] = {-1, 1, 0, 0}; int Y[4] = {0, 0, -1, 1}; int main(){ freopen("input.txt" , "rt", stdin); cin >> T; for(int tc = 1; tc <= T; tc++){ cin >> N >> M; for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ cin >> arr[i][j]; if(arr[i][j] == 2){ Mx = i; My = j; } } } int ans = 0; for(int h = 1; h < N; h++){ for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ visited[i][j] = 0; } } rQueue.reset(); cQueue.reset(); visited[Mx][My] = 1; rQueue.enQueue(Mx); cQueue.enQueue(My); while(rQueue.is_Empty() == false){ int cr = rQueue.deQueue(); int cc = cQueue.deQueue(); for(int i = 0; i < 4; i++){ for(int j = 1; j <= h; j++){ int nr = cr + j*X[i]; int nc = cc + Y[i]; if(nr >= 0 && nr < N && nc >= 0 && nc < M && visited[nr][nc] == 0 && arr[nr][nc] != 0){ if(arr[nr][nc] == 3){ ans = h; goto end; }else{ visited[nr][nc] = 1; rQueue.enQueue(nr); cQueue.enQueue(nc); } } } } } } end: cout << "Case #" << tc << endl; cout << ans << endl; } return 0; }
Leave a Comment