BZOJ3205

bzoj3205.cpp

#include <cstdio>
#include <cstring>
#include <queue>
const int N = 509;
const int d[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
int q[N*N*4][3],h,t,f[10][10][N*N],n,W,H,to[N*N][4],p[N*N],QQ[N*N],tmp[N*N],b[N*N],Q[N*N],used[N*N],Time,pre[N*N];
char map[N][N];
bool inq[N*N];
inline int node(int x,int y){return (x - 1) * W + y;}
inline void Min(int &x,int y){if (x > y) x = y;}
inline void Max(int &x,int y){if (x < y) x = y;}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("3205.in","r",stdin);
    freopen("3205.out","w",stdout);
    #endif
    scanf("%d%d%d\n",&n,&W,&H);
    if (n == 1) puts("0");
    memset(map,'x',sizeof map);
    for (int i = 1; i <= H; ++i) {
        for (int j = 1; j <= W; ++j) scanf("%c",&map[i][j]);
        scanf("\n");
    }
    int tot = 0;
    for (int i = 1; i <= H; ++i)
        for (int j = 1; j <= W; ++j)
            if (map[i][j] != 'x') {
                bool flag = false;
                for (int k = 0; k < 4; ++k) {
                    int nx = i + d[k][0],ny = j + d[k][1];
                    if (map[nx][ny] == 'x') {
                        flag = true;
                        to[node(i,j)][k] = node(i,j);
                        q[++t][0] = i;
                        q[t][1] = j;
                        q[t][2] = k;
                    }
                }
                if (map[i][j] <= '9' && map[i][j] >= '1' || flag) p[++tot] = node(i,j);
            }
    h = 1;
    while (h <= t) {
        int ux = q[h][0],uy = q[h][1],dir = q[h][2],nx,ny,nd; ++h;
        if (map[ux][uy] == 'A') nd = (dir + 1) % 4;
        else if (map[ux][uy] == 'C') nd = (dir - 1 + 4) % 4;
        else nd = dir;
        nx = ux + d[(nd + 2) % 4][0]; ny = uy + d[(nd + 2) % 4][1];
        if (map[nx][ny] != 'x') {
            q[++t][0] = nx; q[t][1] = ny; q[t][2] = nd;
            to[node(nx,ny)][nd] = to[node(ux,uy)][dir];
        }
        //puts("");
    }
    //memset(f,0x3f,sizeof f);
    for (int i = 1; i <= tot; ++i)
        for (int j = 1; j <= n; ++j)
            for (int k = j; k <= n; ++k)
                f[j][k][p[i]] = 0x3f3f3f3f;
    for (int i = 1; i <= H; ++i)
        for (int j = 1; j <= W; ++j)
            if (map[i][j] >= '1' && map[i][j] <= '9')
                f[map[i][j] - '0'][map[i][j] - '0'][node(i,j)] = 0;
    for (int l = 0; l < n; ++l) {
        for (int ii = 1; ii <= tot; ++ii) {
            int i = p[ii];
            for (int j = 1; j + l <= n; ++j) {
                int k = j + l;
                for (int l = j; l < k; ++l)
                    Min(f[j][k][i],f[j][l][i] + f[l + 1][k][i]);
            }
        }
        for (int j = 1; j + l <= n; ++j) {
            int k = j + l;
            int hh,tt,max = 0; tt = 0;
            for (int i = 1; i <= tot; ++i) {
                if (f[j][k][p[i]] == 0x3f3f3f3f) continue;
                QQ[++tt] = p[i];
                Max(max,f[j][k][p[i]]);
            }
            for (int i = 0; i <= max; ++i) b[i] = 0;
            for (int i = 1; i <= tt; ++i) ++b[f[j][k][QQ[i]]],tmp[i] = QQ[i];
            for (int i = 1; i <= max; ++i) b[i] += b[i - 1];
            for (int i = 1; i <= tt; ++i) QQ[b[f[j][k][tmp[i]]]--] = tmp[i];
            hh = 1; h = 1; t = 0;
            ++Time;
            while (hh <= tt || h <= t) {
                int u;
                if (h <= t && (hh > tt || f[j][k][Q[h]] < f[j][k][QQ[hh]])) u = Q[h++];
                else u = QQ[hh++];
                if (used[u] == Time) continue;
                used[u] = Time;
                for (int i = 0,v; i < 4; ++i)
                    if ((v = to[u][i]) && f[j][k][v] > f[j][k][u] + 1) {
                        f[j][k][v] = f[j][k][u] + 1;
                        Q[++t] = v;
                    }
            }
        }
    }
    int ans = 0x3f3f3f3f;
    for (int i = 1; i <= tot; ++i)
        ans = std::min(ans,f[1][n][p[i]]);
    printf("%d\n",(ans == 0x3f3f3f3f ? -1 : ans));
}