P1825 [USACO11OPEN]Corn Maze S

这题wa了有点久。。。对bfs理解更深刻了（bfs第一次扩展到即为最短距离）。

• 大体上和bfs模板差不多，只是增加了传送门，且题意规定一旦到达传送门立即传送。
• 只需要将当前扩展的结点变为传送到的结点即可，在判断dist数组是否为-1
• dist数组即标记数组vis，第一次更新时即为最短。

const int N=310;
char g[N][N];
int dist[N][N];
vector<PII> trans[30];
bool vis[N][N];
int n,m;
PII st,ed;
int cnt;

bool check(int x,int y)
{
    return x>=0 && x<n && y>=0 && y<m;
}

PII find(int u,int x,int y)
{
    for(int i=0;i<trans[u].size();i++)
    {
        PII j=trans[u][i];
        if(j.fi != x || j.se != y)
            return j;
    }
}

int bfs(int x,int y)
{
    memset(dist,-1,sizeof dist);
    queue<PII> q;
    dist[x][y]=0;
    q.push({x,y});

    while(q.size())
    {
        PII t=q.front();
        q.pop();

        //cout<<"---"<<t.fi<<' '<<t.se<<' '<<dist[t.fi][t.se]<<endl;

        if(t.fi == ed.fi && t.se == ed.se) return dist[t.fi][t.se];

        for(int i=0;i<4;i++)
        {
            int a=t.fi+dx[i],b=t.se+dy[i];
            if(!check(a,b)) continue;
            if(g[a][b] == '#') continue;
            if(isupper(g[a][b]))
            {
                PII nxt=find(g[a][b]-'A',a,b);
                a=nxt.fi,b=nxt.se;
            }
            if(dist[a][b] == -1)
            {
                dist[a][b]=dist[t.fi][t.se]+1;
                q.push({a,b});
            }
        }
    }
}

int main()
{
    cin>>n>>m;

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            cin>>g[i][j];
            if(g[i][j] == '=') ed.fi=i,ed.se=j;
            else if(g[i][j] == '@') st.fi=i,st.se=j;
            else if(isupper(g[i][j])) trans[g[i][j]-'A'].push_back({i,j});
        }

    int t=bfs(st.fi,st.se);
    cout<<t<<endl;

    //system("pause");
}