nord vpnnord vpn
Ad

Untitled

mail@pastecode.io avatar
unknown
plain_text
5 months ago
1.7 kB
1
Indexable
Never
#include<iostream>
using namespace std;
#define size 100000
int n, m,ans;
int queue[size];
int front=-1;
int rear=-1;
char map[1000][1000];
int visit[1000][1000];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void reset(){
	for(int i=0; i<1000; i++)
	{
		for(int j=0; j<1000; j++){
			visit[i][j]=99999;
		}

	}

}

bool isEmpty(){
	return front==rear;
}

void push(int x){
	if(rear==size-1) rear=-1;
	rear++;
	queue[rear]=x;
}

int pop(){
	if(front ==-1) front =-1;
	front++;
	return queue[front];
}
void bfs(int x, int y){
	visit[x][y]=1;
	push(x);
	push(y);
	while(!isEmpty()){
		int x1=pop();
		int y1=pop();
		for(int i=0; i<4; i++){
			int x2= x1+dx[i];
			int y2=y1+dy[i];
			if( x2>=0 && x2<n && y2>=0 && y2<m){
				if(map[x2][y2]=='B' && visit[x2][y2]>visit[x1][y1]+1){
					visit[x2][y2]= visit[x1][y1]+2;
					push(x2);
					push(y2);
				}
				if(map[x2][y2]=='E' && visit[x2][y2]>visit[x1][y1]+1){
					visit[x2][y2]= visit[x1][y1]+1;
					push(x2);
					push(y2);
				}
				if(map[x2][y2]=='T' && visit[x2][y2]>visit[x1][y1]+1){
					visit[x2][y2]= visit[x1][y1]+1;
					if(ans>visit[x2][y2]) ans=visit[x2][y2];
				}


			}

		}

	}

}


int main(){
	freopen("text.txt", "r",stdin);
	int t;
	cin>>t;
	for (int testcase = 1; testcase <= t; testcase++)
	{
		cout<<"Case #"<<testcase<<endl;
		reset();

		cin>>n>>m;
		ans=1000000;

		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				cin>>map[i][j];
			}

		}
		for(int i=0; i<n; i++){
			for(int j=0; j<m;j++){
				if(map[i][j]=='Y'){
					bfs(i,j);
				}
			}

		}

		if(ans==1000000){
			cout<<"-1"<<endl;
		}else cout<<ans-1<<endl;

	}

	return 0;
}

nord vpnnord vpn
Ad