Untitled
unknown
plain_text
a year ago
2.4 kB
6
Indexable
#include <iostream> using namespace std; int T, N, M; char arr[305][305]; int x1, y1, x2, y2; class Queue{ int front, rear; int q[1000000]; public: Queue(); void enQueue(int value); int deQueue(); bool is_Empty(); void reset(); }; Queue::Queue(){ front = rear = -1; } void Queue::enQueue(int value){ q[++rear] = value; } int Queue::deQueue(){ return q[++front]; } bool Queue::is_Empty(){ if(front == rear){ return true; }else{ return false; } } void Queue::reset(){ front = rear = -1; } int visited[305][305]; Queue rQueue, cQueue; int X[4] = {-1, 1, 0, 0}; int Y[4] = {0, 0, -1, 1}; void BFS(){ while(!rQueue.is_Empty()){ int cr = rQueue.deQueue(); int cc = cQueue.deQueue(); for(int i = 0; i < 4; i++){ int nr = cr + X[i]; int nc = cc + Y[i]; if(nr >= 0 && nr < N && nc >= 0 && nc < M && arr[nr][nc] != 'S' && arr[nr][nc] != 'R' && visited[nr][nc] == 0){ if(arr[nr][nc] == 'B'){ visited[nr][nc] = visited[cr][cc] + 2; } if(arr[nr][nc] == 'E' || arr[nr][nc] == 'T'){ visited[nr][nc] = visited[cr][cc] + 1; } rQueue.enQueue(nr); cQueue.enQueue(nc); } } } } int main(){ freopen("input.txt", "rt", stdin); cin >> T; for(int tc = 1; tc <= T; tc++){ cin >> N >> M; cin.ignore(); for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ cin >> arr[i][j]; if(arr[i][j] == 'Y'){ x1 = i; y1 = j; } if(arr[i][j] == 'T'){ x2 = i; y2 = j; } visited[i][j] = 0; } } rQueue.reset(); cQueue.reset(); visited[x1][y1] = 1; rQueue.enQueue(x1); cQueue.enQueue(y1); BFS(); cout << "Case #" << tc << endl; if(visited[x2][y2] != 0){ cout << visited[x2][y2] - 1 << endl; }else{ cout << -1 << endl; } } return 0; }
Editor is loading...