Submission #10312

#	Time	Username	Problem	Language	Result	Execution time	Memory
10312		dohyun0324	Robots (APIO13_robots)	C++98	0 / 100	0 ms	149448 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[11][11][510][510],ch[5][510][510],px,py,pk,check[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<int,int> >arr[250010];
struct data
{
    int 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;
    for(k=0;k<arr[p].size();k++)
    {
        r++; q[r].x=arr[p][k].first; q[r].y=arr[p][k].second; q[r].lev=d[i][j][q[r].x][q[r].y]; 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=q[f].lev+1; 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=q[f].lev+1; check[q[r].x][q[r].y]=q[r].lev;
        }
    }
    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) d[j][j+i][k][l]=2147483647;
                        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];
                }
            }
            bfs2(j,j+i,mini);
        }
    }
}
void dfs(int k,int x,int 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];
        }
    }
    printf("%d",dap);
    return 0;
}

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