Untitled

 avatar
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...