我的思路:
用广搜遍历,如果一个点被第一次搜索到,把这个点标记为一个标号,然后连边,入队;如果被少于等于4次搜索到,那么就只连边,并且不入队;如果遇到了一个传送门,那么就连一条权值为0的边,然后跑dijkstra
下面是代码(极度冗长):
#include<bits/stdc++.h>
using namespace std;
char a[305][305],visit[305][305];
int n,m,qd,zd,dbh[305][305];
int bian[305][305];
int cnt,head[100005];
void add(int u,int v,int w){bian[u][v]=w;}
int dis[100005];
struct node{
int u,d;
bool operator<(const node& rhs)const{return d>rhs.d;}
};
void dijkstra(int kaishi,int jieshu){
for(int i=1;i<=n;i++)dis[i]=2147483647;
dis[kaishi]=0;
priority_queue<node>Q;
Q.push((node){kaishi,0});
while(!Q.empty()){
node fr=Q.top();Q.pop();
int u=fr.u,d=fr.d;
if(d!=dis[u])continue;
for(int i=1;i<=n;i++){
if(bian[u][i]!=-1){
int w=bian[u][i];
if(dis[u]+w<dis[i]){
dis[i]=dis[u]+w;
Q.push((node){i,dis[i]});
}
}
}
}
}
void findd(char ch,int xx,int yy,int bhq,int bhz){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]==ch){
visit[i][j]++;
add(bhq,bhz,0);
}
}
void build(int x,int y){
queue<int>qx;queue<int>qy;
qx.push(x);qy.push(y);
int bh=0;
dbh[x][y]=++bh;
while(!qx.empty()){
int dqx=qx.front();qx.pop();
int dqy=qy.front();qy.pop();
if(visit[dqx+1][dqy]<4){
if(a[dqx+1][dqy]=='.'||a[dqx+1][dqy]=='@'){
if(!dbh[dqx+1][dqy]){
dbh[dqx+1][dqy]=++bh;
add(dbh[dqx][dqy],dbh[dqx+1][dqy],1);
visit[dqx+1][dqy]++;
qx.push(dqx+1);qy.push(dqy);
}
else{
add(dbh[dqx][dqy],dbh[dqx+1][dqy],1);
visit[dqx+1][dqy]++;
}
}
if(a[dqx+1][dqy]=='='){
dbh[dqx+1][dqy]=++bh;
add(dbh[dqx][dqy],dbh[dqx+1][dqy],1);
visit[dqx+1][dqy]++;
}
if(a[dqx+1][dqy]<='Z'&&a[dqx+1][dqy]>='A'){
if(!dbh[dqx+1][dqy]){
dbh[dqx+1][dqy]=++bh;
add(dbh[dqx][dqy],dbh[dqx+1][dqy],1);
visit[dqx+1][dqy]++;
findd(a[dqx+1][dqy],dqx+1,dqy,dbh[dqx][dqy],dbh[dqx+1][dqy]);
}
else{
add(dbh[dqx][dqy],dbh[dqx+1][dqy],1);
visit[dqx+1][dqy]++;
}
}
}
if(visit[dqx-1][dqy]<4){
if(a[dqx-1][dqy]=='.'||a[dqx-1][dqy]=='@'){
if(!dbh[dqx-1][dqy]){
dbh[dqx-1][dqy]=++bh;
add(dbh[dqx][dqy],dbh[dqx-1][dqy],1);
visit[dqx-1][dqy]++;
qx.push(dqx-1);qy.push(dqy);
}
else{
add(dbh[dqx][dqy],dbh[dqx-1][dqy],1);
visit[dqx-1][dqy]++;
}
}
if(a[dqx-1][dqy]=='='){
dbh[dqx-1][dqy]=++bh;
add(dbh[dqx][dqy],dbh[dqx-1][dqy],1);
visit[dqx-1][dqy]++;
}
if(a[dqx-1][dqy]<='Z'&&a[dqx-1][dqy]>='A'){
if(!dbh[dqx-1][dqy]){
dbh[dqx-1][dqy]=++bh;
add(dbh[dqx][dqy],dbh[dqx-1][dqy],1);
visit[dqx-1][dqy]++;
findd(a[dqx-1][dqy],dqx-1,dqy,dbh[dqx][dqy],dbh[dqx-1][dqy]);
}
else{
add(dbh[dqx][dqy],dbh[dqx-1][dqy],1);
visit[dqx-1][dqy]++;
}
}
}
if(visit[dqx][dqy+1]<4){
if(a[dqx][dqy+1]=='.'||a[dqx][dqy+1]=='@'){
if(!dbh[dqx][dqy+1]){
dbh[dqx][dqy+1]=++bh;
add(dbh[dqx][dqy],dbh[dqx][dqy+1],1);
visit[dqx][dqy+1]++;
qx.push(dqx);qy.push(dqy+1);
}
else{
add(dbh[dqx][dqy],dbh[dqx][dqy+1],1);
visit[dqx][dqy+1]++;
}
}
if(a[dqx][dqy+1]=='='){
dbh[dqx][dqy+1]=++bh;
add(dbh[dqx][dqy],dbh[dqx][dqy+1],1);
visit[dqx][dqy+1]++;
}
if(a[dqx][dqy+1]<='Z'&&a[dqx][dqy+1]>='A'){
if(!dbh[dqx][dqy+1]){
dbh[dqx][dqy+1]=++bh;
add(dbh[dqx][dqy],dbh[dqx][dqy+1],1);
visit[dqx][dqy+1]++;
findd(a[dqx][dqy+1],dqx-1,dqy,dbh[dqx][dqy],dbh[dqx][dqy+1]);
}
else{
add(dbh[dqx][dqy],dbh[dqx][dqy+1],1);
visit[dqx][dqy+1]++;
}
}
}
if(visit[dqx][dqy-1]<4){
if(a[dqx][dqy-1]=='.'||a[dqx][dqy-1]=='@'){
if(!dbh[dqx][dqy-1]){
dbh[dqx][dqy-1]=++bh;
add(dbh[dqx][dqy],dbh[dqx][dqy-1],1);
visit[dqx][dqy-1]++;
qx.push(dqx);qy.push(dqy-1);
}
else{
add(dbh[dqx][dqy],dbh[dqx][dqy-1],1);
visit[dqx][dqy-1]++;
}
}
if(a[dqx][dqy-1]=='='){
dbh[dqx][dqy-1]=++bh;
add(dbh[dqx][dqy],dbh[dqx][dqy-1],1);
visit[dqx][dqy-1]++;
}
if(a[dqx][dqy-1]<='Z'&&a[dqx][dqy-1]>='A'){
if(!dbh[dqx][dqy-1]){
dbh[dqx][dqy-1]=++bh;
add(dbh[dqx][dqy],dbh[dqx][dqy-1],1);
visit[dqx][dqy-1]++;
findd(a[dqx][dqy-1],dqx-1,dqy,dbh[dqx][dqy],dbh[dqx][dqy-1]);
}
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
bian[i][j]=-1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)cin>>a[i][j];
int bj=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
if(a[i][j]=='.'){build(i,j);bj=1;break;}
if(bj)break;
}
int qishi,jieshu;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(a[i][j]=='@')qishi=dbh[i][j];
if(a[i][j]=='=')jieshu=dbh[i][j];
}
dijkstra(qishi,jieshu);
cout<<dis[jieshu];
return 0;
}