SPFA做法25PTS求条（调出必关）

#include<bits/stdc++.h>
using namespace std;
const int N=300*300*2+5;
int d[N],idx,to[N],w[N],ne[N],h[N];
bool st[N];

char tp[305][305];
struct node
{
    int x1,x2;
    int y1,y2;
};
unordered_map<char,node> hsh;
bool jud[305][305];

int n,m;
void add(int u,int v,int we)
{   
    to[idx]=v;
    w[idx]=we;
    ne[idx]=h[u];
    h[u]=idx++;
}
void spfa(int u)
{
    queue<int>q;
    d[u]=0;
    q.push(u);
    st[u]=1;
    while(q.size())
    {
        int k=q.front();
        q.pop();
        st[k]=0;
        for(int i=h[k];i!=-1;i=ne[i])
        {
            int j=to[i];
            if(d[j]>d[k]+w[i])
            {
                d[j]=d[k]+w[i];
                if(!st[j])
                {
                    q.push(j);
                    st[j]=1;               
                }

            }
        }
    }
}
int bxh(int x,int y)
{
    return (x-1)*m+y;
}
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int main()
{
    memset(h,-1,sizeof h);
    memset(d,0x3f,sizeof d);
    cin>>n>>m;
    int ed=0,str=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>tp[i][j];
            if(tp[i][j]!='.'&&tp[i][j]!='#'&&tp[i][j]!='='&&tp[i][j]!='@')
            {
                jud[i][j]=1;
                if(!hsh[tp[i][j]].x1)
                {
                    hsh[tp[i][j]].x1=i;
                    hsh[tp[i][j]].y1=j;
                }
                else
                {
                    add(bxh(hsh[tp[i][j]].x1,hsh[tp[i][j]].y1),bxh(i,j),0);
                    add(bxh(i,j),bxh(hsh[tp[i][j]].x1,hsh[tp[i][j]].y1),0);
                    jud[i][j]=1;
                    jud[hsh[tp[i][j]].x1][hsh[tp[i][j]].y1]=1;
                }
            }
            if(tp[i][j]=='=')
                ed=bxh(i,j);    
            if(tp[i][j]=='@')
                str=bxh(i,j);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(!jud[i][j]&&tp[i][j]!='#')
            {
                for(int k=0;k<4;k++)
                {
                    int tx=i+dx[k];
                    int ty=j+dy[k];
                    if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&tp[tx][ty]!='#') 
                    {
                        add(bxh(i,j),bxh(tx,ty),1);
                        add(bxh(tx,ty),bxh(i,j),1);
                    }
                }
            }
        }
    }
    spfa(str);
    cout<<d[ed];
    return 0;
}