Untitled
unknown
plain_text
2 years ago
1.7 kB
9
Indexable
#include <iostream>
using namespace std;
class Queue
{
private:
int front, rear;
int Data[90000];
public:
Queue();
void reset();
void enQueue(int value);
int deQueue();
bool is_Empty();
};
Queue::Queue(){
front=rear=-1;
}
void Queue::reset(){
front=rear=-1;
}
void Queue::enQueue(int value){
Data[++rear]=value;
}
int Queue::deQueue(){
return Data[++front];
}
bool Queue::is_Empty(){
if (front==rear)
return true;
return false;
}
Queue rQueue, cQueue;
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
int nr, nc, cr, cc;
int main(){
freopen ("input.txt", "r", stdin);
int T, N, M, Y_x, Y_y, T_x, T_y;
int Map[300][300];
char Arr[300][300];
bool visit[300][300];
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];
visit[i][j]=false;
Map[i][j]=0;
if (Arr[i][j]=='Y'){
Y_x=i;
Y_y=j;
}
else if (Arr[i][j]=='T'){
T_x=i;
T_y=j;
}
}
}
rQueue.reset();
cQueue.reset();
rQueue.enQueue(Y_x);
cQueue.enQueue(Y_y);
visit[Y_x][Y_y]=true;
while (rQueue.is_Empty()==false){
cr=rQueue.deQueue();
cc=cQueue.deQueue();
for (int i=0; i<4; i++){
nr=cr+dx[i];
nc=cc+dy[i];
if (nr>=0 && nr<N && nc>=0 && nc<M &&
visit[nr][nc]==false && Arr[nr][nc]!='S' && Arr[nr][nc]!='R')
{
rQueue.enQueue(nr);
cQueue.enQueue(nc);
visit[nr][nc]=true;
if (Arr[nr][nc]=='E' || Arr[nr][nc]=='T')
Map[nr][nc]=Map[cr][cc]+1;
else if (Arr[nr][nc]=='B')
Map[nr][nc]=Map[cr][cc]+2;
}
}
}
cout<<"Case #"<<tc<<endl<<Map[T_x][T_y]<<endl;
}
return 0;
}
Editor is loading...