Submission #7195

#	Time	Username	Problem	Language	Result	Execution time	Memory
7195		baneling100	Portals (BOI14_portals)	C++98	100 / 100	344 ms	34128 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], D[1001][1001];
int Dy[4]={0,1,0,-1}, Dx[4]={1,0,-1,0};
int Left[1001][1001], Right[1001][1001], Up[1001][1001], Down[1001][1001];

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=1 ; i<=R ; i++)
    {
        x=0;
        for(j=1 ; j<=C ; j++)
        {
            if(A[i][j])
                x=0;
            else
            {
                if(!x)
                    x=j;
                Left[i][j]=x;
            }
        }
        x=0;
        for(j=C ; j>=1 ; j--)
        {
            if(A[i][j])
                x=0;
            else
            {
                if(!x)
                    x=j;
                Right[i][j]=x;
            }
        }
    }
    for(i=1 ; i<=C ; i++)
    {
        x=0;
        for(j=1 ; j<=R ; j++)
        {
            if(A[j][i])
                x=0;
            else
            {
                if(!x)
                    x=j;
                Up[j][i]=x;
            }
        }
        x=0;
        for(j=R ; j>=1 ; j--)
        {
            if(A[j][i])
                x=0;
            else
            {
                if(!x)
                    x=j;
                Down[j][i]=x;
            }
        }
    }
}

void process(void)
{
    int i, j, y, x, ty, tx;

    for(i=0 ; i<=R+1 ; i++)
        for(j=0 ; j<=C+1 ; j++)
        {
            B[i][j]=INF;
            if(i==0 || i==R+1 || j==0 || j==C+1 || A[i][j])
            {
                B[i][j]=0;
                Q.push(i);
                Q.push(j);
            }
        }
    while(!Q.empty())
    {
        y=Q.front();
        Q.pop();
        x=Q.front();
        Q.pop();
        for(i=0 ; i<=3 ; i++)
        {
            ty=y+Dy[i];
            tx=x+Dx[i];
            if(ty>=0 && ty<=R+1 && tx>=0 && tx<=C+1)
                if(B[ty][tx]>B[y][x]+1)
                {
                    B[ty][tx]=B[y][x]+1;
                    Q.push(ty);
                    Q.push(tx);
                }
        }
    }
    D[Sy][Sx]=0;
    Q.push(Sy);
    Q.push(Sx);
    while(!Q.empty())
    {
        y=Q.front();
        Q.pop();
        x=Q.front();
        Q.pop();
        for(i=0 ; i<=3 ; i++)
        {
            ty=y+Dy[i];
            tx=x+Dx[i];
            if(ty>=1 && ty<=R && tx>=1 && tx<=C && !A[ty][tx])
                if(D[ty][tx]>D[y][x]+1)
                {
                    D[ty][tx]=D[y][x]+1;
                    Q.push(ty);
                    Q.push(tx);
                }
        }
        ty=y;
        tx=Left[y][x];
        if(D[ty][tx]>D[y][x]+B[y][x])
        {
            D[ty][tx]=D[y][x]+B[y][x];
            Q.push(ty);
            Q.push(tx);
        }
        ty=y;
        tx=Right[y][x];
        if(D[ty][tx]>D[y][x]+B[y][x])
        {
            D[ty][tx]=D[y][x]+B[y][x];
            Q.push(ty);
            Q.push(tx);
        }
        ty=Up[y][x];
        tx=x;
        if(D[ty][tx]>D[y][x]+B[y][x])
        {
            D[ty][tx]=D[y][x]+B[y][x];
            Q.push(ty);
            Q.push(tx);
        }
        ty=Down[y][x];
        tx=x;
        if(D[ty][tx]>D[y][x]+B[y][x])
        {
            D[ty][tx]=D[y][x]+B[y][x];
            Q.push(ty);
            Q.push(tx);
        }
    }
}

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

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

    return 0;
}

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