bzoj千题计划230：bzoj3205: [Apio2013]机器人

#include
#include
#includeusing namespace std;

#define N 501

typedef pairint,int> pii;

#define MP(x,y) make_pair(x,y)

int T,m,n;
char s[N];

int map[N][N];

int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

int pos[4][N][N];
bool v[4][N][N];

int dp[10][10][N][N];

int tot,mx;
int cnt[N*N*3];
pii tmp[N*N],q[N*N];
queueq1,q2;

bool vis[N][N];

inline int &min(int &x,int &y) { return x x: y; }

bool inmap(int x,int y)
{
    if(x0 || x>n || y0 || y>m) return false;
    if(!map[x][y]) return false;
    return true;
}

int find(int x,int y,int d)
{
    if(pos[d][x][y]) return pos[d][x][y];
    if(!map[x][y]) return -2;
    if(v[d][x][y]) return -1;
    v[d][x][y]=true;
    int nd=d;
    if(map[x][y]==-1) nd=(d-1+4)%4;
    if(map[x][y]==-2) nd=(d+1)%4;
    int npos=-1;
    if(!inmap(x+dx[nd],y+dy[nd])) npos=-2; 
    else npos=find(x+dx[nd],y+dy[nd],nd);
    v[d][x][y]=false;
    if(npos==-2) return pos[d][x][y]=(x-1)*m+y; 
    else return pos[d][x][y]=npos;
}

void spfa(int l,int r)
{
      for(int i=0;i0;
    for(int i=1;i;
    for(int i=1;i1];
    for(int i=tot;i;--i) q[cnt[dp[l][r][tmp[i].first][tmp[i].second]]--]=tmp[i];
    for(int i=1;ii) q2.push(q[i]);
    int x,y,nx,ny;
    while(!q2.empty() || !q1.empty())
    {
        if(q1.empty()) 
        {
            x=q2.front().first; 
            y=q2.front().second; 
            q2.pop();
        }
        else if(q2.empty())
        {
            x=q1.front().first; 
            y=q1.front().second; 
            q1.pop();
            vis[x][y]=false;
        }
        else if(dp[l][r][q1.front().first][q1.front().second]>dp[l][r][q2.front().first][q2.front().second])
        {
            x=q2.front().first; 
            y=q2.front().second; 
            q2.pop();
        }
        else
        {
            x=q1.front().first; 
            y=q1.front().second; 
            q1.pop();
            vis[x][y]=false;
        }
        for(int i=0;i4;++i)
        {
            if(pos[i][x][y]==-1) continue;
            nx=(pos[i][x][y]-1)/m+1; 
            ny=pos[i][x][y]-(nx-1)*m;
            if(dp[l][r][x][y]+1dp[l][r][nx][ny])
            {
                dp[l][r][nx][ny]=dp[l][r][x][y]+1;
                if(!vis[nx][ny]) q1.push(MP(nx,ny)),vis[nx][ny]=true;
            }
        }
    }
}

int main()
{
    scanf("%d%d%d",&T,&m,&n);
    for(int i=1;ii)
    {
        scanf("%s",s+1);
        for(int j=1;jj)
            if(s[j]==‘A‘) map[i][j]=-1;
            else if(s[j]==‘C‘) map[i][j]=-2;
            else if(s[j]>=‘1‘ && s[j]‘9‘) map[i][j]=s[j]-‘0‘;
            else if(s[j]==‘.‘) map[i][j]=10;
    }
    for(int d=0;d4;++d)
    {
        for(int i=1;ii)
            for(int j=1;jj)
                if(map[i][j]) find(i,j,d);
    }
    memset(dp,63,sizeof(dp));
    int oo=dp[0][0][0][0];
    for(int i=1;ii)
        for(int j=1;jj)
            if(map[i][j]>=1 && map[i][j]9) dp[map[i][j]][map[i][j]][i][j]=0;
    for(int i=T;i;--i)
        for(int j=i;jj)
        {
            tot=mx=0;
            for(int x=1;xx)
                for(int y=1;yy)
                {
                    for(int k=i;kk)
                        dp[i][j][x][y]=min(dp[i][j][x][y],dp[i][k][x][y]+dp[k+1][j][x][y]);
                    if(dp[i][j][x][y]!=oo) tmp[++tot]=MP(x,y),mx=max(mx,dp[i][j][x][y]);
                }
            if(tot) spfa(i,j);
        }
    int ans=oo;
    for(int i=1;ii)
        for(int j=1;jj)
            ans=min(ans,dp[1][T][i][j]);
    if(ans==oo) printf("-1");
    else printf("%d",ans);
    return 0;
}