打了标记:https://www.luogu.com.cn/record/201376314
没打标记:https://www.luogu.com.cn/record/201376415
这是我没打标记的
#include<bits/stdc++.h>
using namespace std;
int n,m,ans=1e8;
bool vis[305][305];
int ax,ay,bx,by;
char a[305][305];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
vector<int> v[150];
struct qaq
{
int x,y,t;
};
queue<qaq> q;
map<pair<int,int>,pair<int,int>> mp;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
if(a[i][j]=='@')
{
ax=i;
ay=j;
}
if(a[i][j]=='=')
{
bx=i;
by=j;
}
if(a[i][j]>='A'&&a[i][j]<='Z')
{
//cout<<"qwq";
v[(int)a[i][j]].push_back(i);
v[(int)a[i][j]].push_back(j);
}
}
}
// for(int i:v['W'])
// {
// cout<<i<<' ';
// }
// cout<<'\n';
for(int qwq='A';qwq<='Z';qwq++)
{
if(v[qwq].size()!=0)
{
int i=v[qwq][0];
int j=v[qwq][1];
int ii=v[qwq][2];
int jj=v[qwq][3];
mp[make_pair(i,j)]=make_pair(ii,jj);
mp[make_pair(ii,jj)]=make_pair(i,j);
}
}
vis[ax][ay]=1;
q.push({ax,ay,0});
while(!q.empty())
{
qaq now=q.front();
q.pop();
if(now.x==bx && now.y==by)
{
ans=min(ans,now.t);
continue;
}
if(a[now.x][now.y]>='A'&&a[now.x][now.y]<='Z')
{
int x=mp[make_pair(now.x,now.y)].first;
int y=mp[make_pair(now.x,now.y)].second;
//cout<<"awa"<<' '<<x<<' '<<y<<'\n';
//vis[x][y]=1;
for(int i=0;i<4;i++)
{
int ii=x+dx[i];
int jj=y+dy[i];
if(ii>=1&&ii<=n&&jj>=1&&jj<=m&&(!vis[ii][jj]||(ii==bx&&jj==by))&&a[ii][jj]!='#')
{
q.push({ii,jj,now.t+1});
vis[ii][jj]=1;
//cout<<ii<<' '<<jj<<"qaq\n";
}
}
}
else
{
for(int i=0;i<4;i++)
{
int ii=now.x+dx[i];
int jj=now.y+dy[i];
if(ii>=1&&ii<=n&&jj>=1&&jj<=m&&!vis[ii][jj]&&a[ii][jj]!='#')
{
q.push({ii,jj,now.t+1});
vis[ii][jj]=1;
//cout<<ii<<' '<<jj<<"awa\n";
}
}
}
}
cout<<ans;
return 0;
}
把vis[x][y]=1
的注释取消就变成没打标记的了