测试点3、4、10、14 TLE,测试点1、13、15 AC,其余测试点WA。
代码在这里:
#include<bits/stdc++.h>
using namespace std;
const int N=310;
const int DY[4]={-1,1,0,0};
const int DX[4]={0,0,-1,1};
int a[N][N],d[N][N];
struct Node
{
int x;
int y;
};
queue<Node>q;
char s[N];
Node tp[52];
int n,m,dx,dy,tx,ty;
long long ans=0;
bool check(int x,int y)
{
return x>=1&&x<=m&&y>=1&&y<=n;
}
int BFS(int x,int y,int tx,int ty)
{
memset(d,-1,sizeof(d));
q.push((Node){x,y});
d[x][y]=0;
while(!q.empty()){
Node p=q.front();
q.pop();
if(p.x==tx&&p.y==ty){
return d[p.x][p.y];
}
if(a[p.x][p.y]>=0){
int tmp=a[p.x][p.y];
if(tmp+26>52){
p.x=tp[tmp-26].x;
p.y=tp[tmp-26].y;
}else{
p.x=tp[tmp+26].x;
p.y=tp[tmp+26].y;
}
d[p.x][p.y]=d[tp[tmp].x][tp[tmp].y];
q.push((Node){p.x,p.y});
}
for(int i=0;i<4;++i){
int ax=p.x+DX[i],ay=p.y+DY[i];
if(check(ax,ay)&&a[ax][ay]!=-2&&d[ax][ay]==-1){
d[ax][ay]=d[p.x][p.y]+1;
q.push((Node){ax,ay});
}
}
}
}
int main()
{
memset(tp,0,sizeof(tp));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%s",s+1);
for(int j=1;j<=m;++j){
if(s[j]=='#'){
a[i][j]=-2;
}else{
a[i][j]=-1;
if(s[j]=='@'){
dx=i,dy=j;
}
if(s[j]=='='){
tx=i,ty=j;
}
if(s[j]>='A'&&s[j]<='Z'){
int tmp=s[j]-'A';
if(tp[tmp].x!=0){
tmp+=26;
}
tp[tmp].x=i;
tp[tmp].y=j;
a[i][j]=tmp;
}
}
}
}
ans=BFS(dx,dy,tx,ty);
printf("%lld",ans);
return 0;
}