URAL/1643

来自"NOCOW"

两遍BFS。。。

#include <iostream>
#include <cstring>
using namespace std;
const int dx[]={-1,0,1,0,1,-1,-1,1};
const int dy[]={0,-1,0,1,1,-1,1,-1};
int n,m,l,r,ans=0x7FFFFFFF,tot[26]={0},f[101][101],g[101][101];
char map[110][110];
struct Point
{
    int x,y;
}u,v,target,army[2],port[26][10001],Q[100001];
bool InQ[101][101];
inline void updata(int& dist,const int& w)
{
    if (w < dist)
    {
        dist=w;
        if (!InQ[v.y][v.x])
        {
            Q[++r]=v;
            InQ[v.y][v.x]=true;
        }
    }
}
inline bool operator == (const Point& a,const Point& b)
{
    return (a.x == b.x) && (a.y == b.y);
}
inline void spfa(const Point& S,int dist[101][101])
{
    memset(dist,44,sizeof(int [101][101]));
    l=0,r=1;
    Q[1]=S;
    dist[S.y][S.x]=0;
    while (l < r)
    {
        u=Q[++l];
        int& w=dist[u.y][u.x];
        for (int i=0;i<8;++i)
        {
            v.x=u.x+dx[i];
            v.y=u.y+dy[i];
            if ((v.x < 1) || (v.y < 1) || (v.x > m) || (v.y > n))
                continue;
            if ((map[v.y][v.x] == '#') || (map[v.y][v.x] == '*'))
                continue;
            updata(dist[v.y][v.x],w+1);
        }
        if (('A' <= map[u.y][u.x]) && (map[u.y][u.x] <= 'Z'))
            for (int i=tot[map[u.y][u.x]-'A'];i>0;--i)
            {
                v=port[map[u.y][u.x]-'A'][i];
                if (v == u)  continue;
                updata(dist[v.y][v.x],w);
            }
        InQ[u.y][u.x]=false;
    }
}
int main()
{
    cin >> n >> m;
    memset(tot,0,sizeof(tot));
    for (int i=1;i<=n;++i)
        cin >> &map[i][1];
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j)
        {
            if (map[i][j] == '!')
                army[0].x=j,army[0].y=i;
            else if (map[i][j] == '$')
                army[1].x=j,army[1].y=i;
            else if (map[i][j] == '*')
                target.x=j,target.y=i;
            else if (('A' <= map[i][j]) && (map[i][j] <= 'Z'))
            {
                int tmp=map[i][j]-'A';
                ++tot[tmp];
                port[tmp][tot[tmp]].x=j;
                port[tmp][tot[tmp]].y=i;
            }
        }
    memset(InQ,false,sizeof(InQ));
    spfa(army[0],f);
    spfa(army[1],g);
    for (int i=0;i<8;++i)
    {
        v.x=target.x+dx[i];
        v.y=target.y+dy[i];
        if ((v.x < 1) || (v.y < 1) || (v.x > m) || (v.y > n))
            continue;
        if (map[v.y][v.x] == '#')
            continue;
        ans=min(ans,max(f[v.y][v.x],g[v.y][v.x])+1);
    }
    if (ans < (1<<29))
        cout << ans << endl;
    else
        cout << "Impossible" << endl;
    return 0;
}
//by zzy