Untitled

 avatar
unknown
plain_text
2 years ago
1.7 kB
7
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...