Untitled
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; }