Submission #10357

#	Time	Username	Problem	Language	Result	Execution time	Memory
10357		dohyun0324	Robots (APIO13_robots)	C++98	100 / 100	428 ms	130176 KiB

robots

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
//1 : 동
//2 : 서
//3 : 남
//4 : 북
int mini,dap=2147483647,n,w,h,d[10][10][510][510],px,py,pk,check[510][510];
bool ch[5][510][510];
int xx[5]={0,0,0,1,-1};
int yy[5]={0,1,-1,0,0};
char b[510],a[510][510];
vector< pair<short,short> >arr[250010];
struct data
{
    short x,y;
}go[5][510][510];
struct data2
{
    int x,y,lev;
}q[250010];
struct data3
{
    int x,y;
}pos[11];
void bfs2(int i,int j,int p)
{
    int k,f=-1,r=-1,kx,ky,l;
    while(1)
    {
        f=-1, r=-1;
        for(k=0;k<arr[p].size();k++)
        {
            if(check[arr[p][k].first][arr[p][k].second]) continue;
            r++; q[r].x=arr[p][k].first; q[r].y=arr[p][k].second; q[r].lev=p; check[q[r].x][q[r].y]=q[r].lev;
        }
        arr[p].clear();
        while(f!=r)
        {
            f++;
            p=q[f].lev+1;
            for(k=0;k<arr[p].size();k++)
            {
                if(check[arr[p][k].first][arr[p][k].second]) continue;
                r++; q[r].x=arr[p][k].first; q[r].y=arr[p][k].second; q[r].lev=p; check[q[r].x][q[r].y]=q[r].lev;
            }
            arr[p].clear();
            for(k=1;k<=4;k++)
            {
                kx=go[k][q[f].x][q[f].y].x; ky=go[k][q[f].x][q[f].y].y;
                if(check[kx][ky]) continue;
                r++;
                q[r].x=kx; q[r].y=ky; q[r].lev=p; check[q[r].x][q[r].y]=q[r].lev;
            }
        }
        for(p=p;p<=w*h;p++) if(arr[p].size()) break;
        if(p==w*h+1) break;
    }
    for(k=1;k<=h;k++)
        for(l=1;l<=w;l++)
            if(check[k][l]) d[i][j][k][l]=check[k][l];
}
void dp()
{
    int i,j,k,l,r;
    for(i=1;i<=n-1;i++){
        for(j=1;j<=n-i;j++){
            memset(check,0,sizeof check); mini=2147483647;
            for(r=j;r<j+i;r++){
                for(k=1;k<=h;k++){
                    for(l=1;l<=w;l++){
                        if(r==j) d[j][j+i][k][l]=2147483647;
                        if(d[j][r][k][l]==2147483647 || d[r+1][j+i][k][l]==2147483647) continue;
                        else d[j][j+i][k][l]=min(d[j][j+i][k][l],d[j][r][k][l]+d[r+1][j+i][k][l]);
                    }
                }
            }
            for(k=1;k<=h;k++){
                for(l=1;l<=w;l++){
                    if(d[j][j+i][k][l]!=2147483647) arr[d[j][j+i][k][l]].push_back(make_pair(k,l));
                    if(mini>d[j][j+i][k][l]) mini=d[j][j+i][k][l];
                }
            }
            if(mini!=2147483647) bfs2(j,j+i,mini);
        }
    }
}
void dfs(short k,short x,short y)
{
    int i,l;
    if(ch[k][x][y]==1 || a[x][y]==0 || a[x][y]=='x'){px=x; py=y; pk=k; return;}
    ch[k][x][y]=1;
    if(a[x][y]=='.' || ('1'<=a[x][y] && a[x][y]<='9')) dfs(k,x+xx[k],y+yy[k]);
    else if(a[x][y]=='C'){
        if(k==1) l=3; if(k==3) l=2; if(k==2) l=4; if(k==4) l=1;
        dfs(l,x+xx[l],y+yy[l]);
    }
    else if(a[x][y]=='A'){
        if(k==1) l=4; if(k==4) l=2; if(k==2) l=3; if(k==3) l=1;
        dfs(l,x+xx[l],y+yy[l]);
    }
    if(ch[pk][px][py]==1) go[k][x][y].x=go[pk][px][py].x, go[k][x][y].y=go[pk][px][py].y;
    else go[k][x][y].x=x, go[k][x][y].y=y;
    px=x; py=y; pk=k;
}
void bfs()
{
    int i,j,f=-1,r=0,kx,ky,k;
    for(i=1;i<=n;i++){
        q[0].x=pos[i].x; q[0].y=pos[i].y; q[0].lev=0; f=-1; r=0; memset(check,0,sizeof check); check[pos[i].x][pos[i].y]=1;
        while(f!=r){
            f++;
            for(j=1;j<=4;j++){
                kx=go[j][q[f].x][q[f].y].x; ky=go[j][q[f].x][q[f].y].y;
                if(check[kx][ky]==1) continue;
                check[kx][ky]=1;
                r++; q[r].x=kx; q[r].y=ky; q[r].lev=q[f].lev+1;
                d[i][i][kx][ky]=q[r].lev;
            }
        }
        for(j=1;j<=h;j++){
            for(k=1;k<=w;k++){
                if(d[i][i][j][k]==0 && (j!=pos[i].x || k!=pos[i].y)) d[i][i][j][k]=2147483647;
            }
        }
    }
}
int main()
{
    int i,j,k;
    scanf("%d %d %d",&n,&w,&h);
    for(i=1;i<=h;i++){
        scanf("%s",b);
        for(j=1;j<=w;j++){
            a[i][j]=b[j-1];
            if(1<=(a[i][j]-'0') && (a[i][j]-'0')<=9) pos[a[i][j]-'0'].x=i, pos[a[i][j]-'0'].y=j;
        }
    }
    for(i=1;i<=h;i++)
        for(j=1;j<=w;j++)
            for(k=1;k<=4;k++)
                dfs(k,i,j);

    bfs();
    dp();
    for(i=1;i<=h;i++)
        for(j=1;j<=w;j++)
            if(dap>d[1][n][i][j]) dap=d[1][n][i][j];

    if(dap==2147483647) printf("-1");
    else printf("%d",dap);
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40