Submission #6153

#	Time	Username	Problem	Language	Result	Execution time	Memory
6153		baneling100	Portals (BOI14_portals)	C++98	20 / 100	4 ms	40460 KiB

portals

#include <stdio.h>
#include <queue>
#define INF 0x7fffffff

using namespace std;

queue <int> q;
int R, C, Sy, Sx, Cy, Cx, A[1002][1002], B[1002][1002][4][2], D[1002][1002];
int dy[4]={0,1,0,-1}, dx[4]={1,0,-1,0};

void input(void)
{
    int i, j, x;
    char temp[1002];

    scanf("%d %d",&R,&C);
    for(i=1 ; i<=R ; i++)
    {
        scanf("%s",&temp[1]);
        for(j=1 ; j<=C ; j++)
        {
            if(temp[j]=='#')
                A[i][j]=1;
            else if(temp[j]=='S')
            {
                Sy=i;
                Sx=j;
            }
            else if(temp[j]=='C')
            {
                Cy=i;
                Cx=j;
            }
            D[i][j]=INF;
        }
    }
    for(i=0 ; i<=R+1 ; i++)
        for(j=0 ; j<=C+1 ; j++)
            if(i==0 || i==R+1 || j==0 || j==C+1)
                A[i][j]=1;
    for(i=0 ; i<=R+1 ; i++)
    {
        for(j=0 ; j<=C+1 ; j++)
        {
            if(A[i][j])
                x=j;
            else
            {
                B[i][j][2][0]=i;
                B[i][j][2][1]=x+1;
            }
        }
        for(j=C+1 ; j>=0 ; j--)
        {
            if(A[i][j])
                x=j;
            else
            {
                B[i][j][0][0]=i;
                B[i][j][0][1]=x-1;
            }
        }
    }
    for(i=0 ; i<=C+1 ; i++)
    {
        for(j=0 ; j<=R+1 ; j++)
        {
            if(A[j][i])
                x=j;
            else
            {
                B[j][i][3][0]=x+1;
                B[j][i][3][1]=i;
            }
        }
        for(j=R+1 ; j>=0 ; j--)
        {
            if(A[j][i])
                x=j;
            else
            {
                B[j][i][1][0]=x-1;
                B[j][i][1][1]=i;
            }
        }
    }
}

void process(void)
{
    int i, y, x, ty, tx, check[4], ok;

    D[Sy][Sx]=0;
    q.push(Sy);
    q.push(Sx);
    while(!q.empty())
    {
        y=q.front();
        q.pop();
        x=q.front();
        q.pop();
        check[0]=check[1]=check[2]=check[3]=ok=0;
        for(i=0 ; i<4 ; i++)
        {
            ty=y+dy[i];
            tx=x+dx[i];
            if(A[ty][tx])
                check[i]=ok=1;
            else
                if(D[ty][tx]>D[y][x]+1)
                {
                    D[ty][tx]=D[y][x]+1;
                    q.push(ty);
                    q.push(tx);
                }
        }
        if(ok)
            for(i=0 ; i<4 ; i++)
                if(check[i]==0)
                    if(D[B[y][x][i][0]][B[y][x][i][1]]>D[y][x]+1)
                    {
                        D[B[y][x][i][0]][B[y][x][i][1]]=D[y][x]+1;
                        q.push(B[y][x][i][0]);
                        q.push(B[y][x][i][1]);
                    }
    }
}

void output(void)
{
    printf("%d",D[Cy][Cx]);
}

int main(void)
{
    input();
    process();
    output();

    return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30