oj.uz

Submission #12716

# Submission time Handle Problem Language Result Execution time Memory
12716 2015-01-01T17:31:58 Z baneling100 Robots (APIO13_robots) C++
60 / 100
 1500 ms 113576 KB 
#include <stdio.h>
#include <vector>
#include <queue>
#define INF 0x7fffffff

using namespace std;

typedef pair <int,int> ppair;
typedef pair <int,ppair> pppair;
priority_queue <pppair,vector<pppair>,greater<pppair> > Q;
int N, W, H, Ynext[501][501][4], Xnext[501][501][4], Yloc[10], Xloc[10];
int Ydir[4]={0,1,0,-1}, Xdir[4]={1,0,-1,0}, D[10][10][501][501], Ans=INF;
int Check[501][501][4];
char Room[501][502];

void DFS(int y, int x, int dir) {

    int ty, tx, tdir=dir;

    if(Check[y][x][dir])
        return;
    if(Room[y][x]=='A') {
        tdir=dir-1;
        if(tdir<0)
            tdir=3;
    }
    else if(Room[y][x]=='C') {
        tdir=dir+1;
        tdir%=4;
    }
    ty=y+Ydir[tdir];
    tx=x+Xdir[tdir];
    if(!(ty>=1 && ty<=H && tx>=1 && tx<=W) || Room[ty][tx]=='x') {
        Ynext[y][x][dir]=y;
        Xnext[y][x][dir]=x;
    }
    else {
        DFS(ty,tx,tdir);
        Ynext[y][x][dir]=Ynext[ty][tx][tdir];
        Xnext[y][x][dir]=Xnext[ty][tx][tdir];
    }
    Check[y][x][dir]=1;
}

void renew(int p, int q) {

    int i, j, cost, y, x;

    for(i=1 ; i<=H ; i++)
        for(j=1 ; j<=W ; j++)
            if(D[p][q][i][j]!=INF)
                Q.push(make_pair(D[p][q][i][j],make_pair(i,j)));
    while(!Q.empty()) {
        cost=Q.top().first;
        y=Q.top().second.first;
        x=Q.top().second.second;
        Q.pop();
        if(cost!=D[p][q][y][x])
            continue;
        for(i=0 ; i<=3 ; i++)
            if(D[p][q][Ynext[y][x][i]][Xnext[y][x][i]]>D[p][q][y][x]+1) {
                D[p][q][Ynext[y][x][i]][Xnext[y][x][i]]=D[p][q][y][x]+1;
                Q.push(make_pair(D[p][q][Ynext[y][x][i]][Xnext[y][x][i]],make_pair(Ynext[y][x][i],Xnext[y][x][i])));
            }
    }
}

int main(void) {

    int i, j, k, l, y, x, dir, py, px;

    scanf("%d %d %d",&N,&W,&H);
    for(i=1 ; i<=H ; i++) {
        scanf("%s",&Room[i][1]);
        for(j=1 ; j<=W ; j++)
            if('1'<=Room[i][j] && Room[i][j]<='9') {
                Yloc[Room[i][j]-'0']=i;
                Xloc[Room[i][j]-'0']=j;
                Room[i][j]='.';
            }
    }
    for(i=1 ; i<=H ; i++)
        for(j=1 ; j<=W ; j++)
            if(Room[i][j]!='x')
                for(k=0 ; k<=3 ; k++)
                    DFS(i,j,k);
    for(k=1 ; k<=N ; k++) {
        for(i=1 ; i<=H ; i++)
            for(j=1 ; j<=W ; j++)
                D[k][k][i][j]=INF;
        D[k][k][Yloc[k]][Xloc[k]]=0;
        renew(k,k);
    }
    for(i=1 ; i<=N-1 ; i++)
        for(j=i+1 ; j<=N ; j++)
            for(y=1 ; y<=H ; y++)
                for(x=1 ; x<=W ; x++)
                    D[i][j][y][x]=INF;
    for(l=1 ; l<=N-1 ; l++)
        for(i=1 ; i<=N-l ; i++) {
            j=i+l;
            for(k=i ; k<=j-1 ; k++)
                for(y=1 ; y<=H ; y++)
                    for(x=1 ; x<=W ; x++)
                        if(D[i][k][y][x]!=INF && D[k+1][j][y][x]!=INF && D[i][j][y][x]>D[i][k][y][x]+D[k+1][j][y][x])
                            D[i][j][y][x]=D[i][k][y][x]+D[k+1][j][y][x];
            renew(i,j);
        }
    for(i=1 ; i<=H ; i++)
        for(j=1 ; j<=W ; j++)
            if(Ans>D[1][N][i][j])
                Ans=D[1][N][i][j];
    if(Ans==INF)
        printf("-1");
    else
        printf("%d",Ans);
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 111268 KB Output is correct
2 Correct 0 ms 111268 KB Output is correct
3 Correct 0 ms 111268 KB Output is correct
4 Correct 0 ms 111268 KB Output is correct
5 Correct 0 ms 111268 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 111268 KB Output is correct
2 Correct 0 ms 111268 KB Output is correct
3 Correct 0 ms 111268 KB Output is correct
4 Correct 0 ms 111268 KB Output is correct
5 Correct 0 ms 111268 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 111848 KB Output is correct
2 Correct 8 ms 111268 KB Output is correct
3 Correct 20 ms 111268 KB Output is correct
4 Correct 640 ms 112424 KB Output is correct
5 Correct 76 ms 111652 KB Output is correct

Subtask #4
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 111268 KB Output is correct
2 Execution timed out 1500 ms 113576 KB Program timed out
3 Halted 0 ms 0 KB -