3205: [Apio2013]机器人

Time Limit: 15 Sec Memory Limit: 128 MB
Submit: 79 Solved: 19
[Submit][Status]
Description

VRI(Voltron机器人学会)的工程师建造了 n个机器人。任意两个兼容的机器人站在同一个格子时可以合并为一个复合机器人。我们把机器人用 1至 n编号(n ≤ 9)。如果两个机器人的编号是连续的,那么它们是兼容的,可以合并成一个复合机器人。最初这 n 个机器人各自都只有唯一的编号。而一个由两个或以上的机器人合并构成的复合机器人拥有两个编号,分别是构成它的所有机器人中最小和最大的编号。例如, 2号机器人只可以与 1号或 3号机器人合并。若 2号机器人与 3号机器人合并,可构成编号为 2-3的复合机器人。如果编号为 2-3的复合机器人与编号为 4-6的复合机器人合并,可构成编号为 2-6的复合机器人。当所有机器人合并以后则构成 1-n复合机器人。工程师把这 n个机器人放在了一个封闭的房间中,房间四周均是墙。该房间被划分成 w h 个方格。有些方格有障碍物,机器人不可经过或停留;其余方格允许多个机器人停留,同时允许机器人经过。任何时候一个机器人只占用一个方格。初始时刻,所有机器人均在不同的方格中。这些原始的机器人不会自发地移动。它们只有被工程师沿 x轴或 y轴推动后,才会沿推动的方向不断向前直线移动,直至碰到障碍物或墙停止移动。停止移动后,它会扫描当前的格子是否存在可以与它合并的机器人,如果有,则合并并继续检查,直至不能再合并为止。工程师只能沿水平向左、水平向右、竖直向上、竖直向下四个方向推动机器人,并且,在机器人尚未停止移动时,不允许推动其它机器人,因此任何时刻,房间中都只能有一个机器人移动,为了帮助机器人转向,工程师在一些格子中放置了转向器。具体地说,转向器分为顺时针转向器(右转器)和逆时针转向器(左转器),顺时针转向器可以使到达该格子的机器人沿顺时针方向转向 90_;逆时针转向器可以使到达该格子的机器人沿逆时针方向转向 90_。现在,我们将告诉你初始时刻房间内的信息。请你计算工程师最少共计需要推动机器人多少次,才能把所有的 n个机器人全部合并(如果可能的话)。

Input

你的程序必须从标准输入读入。输入的第 1行包含 3个整数 n、w和 h,用空格隔开。输入文件中接下来的 h行描述初始时刻房间内的信息,每行包含w个字符。这w* h 字符中每一个表示房间中的一个格子,意义如下:

‘ 1’至‘9’:表示该方格中有一个机器人,编号为这个数字;
‘ x’:表示该方格有障碍物;

‘ A’:表示该方格中有一个逆时针转向器;

‘ C’:表示该方格中有一个顺时针转向器;
‘ .’:表示该方格为空地。

Output

你的程序必须输出到标准输出。输出仅一个整数,表示最少需要推动的次数。
若不能使所有机器人全部合并,输出-1。

Sample Input

4 10 5

1.........

AA...x4...

..A..x....

2....x....

..C.3.A...

Sample Output

5

HINT

第一步:向右推动 3 号机器人,当它碰到转向器后会向上继续移动,直至碰到墙壁停止移动。第二步:向上推动 4 号机器人,当它碰到墙壁后停止移动,与3 号机器人合并,构成 3-4 号机器人 第三步:向上推动 2 号机器人,当它碰到转向器后会向左移动,由于左侧为墙壁,故停留在原地。第四步:向右推动 2 号机器人,由于它在一个转向器上,故它会向上移动,直至碰到墙壁停止移动,与 1 号机器人合并,构成 1-2 号机器人。第五步:向左推动 3-4 号机器人,当它碰到墙壁后停止移动,与 1-2 号机器人合并,构成 1-4 号机器人。

n ≤ 9,w ≤ 500 且 h ≤ 500

Source

这题坑了我好久。。必须写篇题解发泄一下

首先,明显是dp

预处理出每个点往每个方向走会走到哪里。

然后F[i][j][k]代表机器人i到j合并到k的最少步数。

第一个转移很简单,暴力for就好了。
关键是第二个。
一开始我直接spfa,然后t成狗。然后改成优先队列,还是t成狗。。然后去查题解,发现了一个很厉害的做法。

对于一张边权都是1的图做多源最短路,有线性的做法:
开两个队列,第一个队列初始为空,第二个队列把每个源按距离从小到大顺序加入。
每次取出两个队列队头的最小值,用这个点去松弛,然后把松弛过的点加入第一个队列。

这样能够保证第一个队列的值都是从小到大递增的。然后就可以实现优先队列的效果了。然后就是线性的了.

Orz

对于这题,第二个队列的排序我们可以用基数排序,这样每次最短路就只要的时间。
加上第一个转移的复杂度,总复杂度就是

PS 这题卡常数。。。我一开始的状态是f[N * N][10][10],然后就华丽丽的tle,改成f[10][10][N * N],就过了!而且时间在八中上是第一。。
就这个坑了我一个多小时。。。

代码

#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));
}

Comments

comments powered by Disqus
Copyright © 2013 lazycal of Shen Ben
Powered by Logdown and Greyshade
Favicon from The Noun Project