Submission #6089

#	Time	Username	Problem	Language	Result	Execution time	Memory
6089		baneling100	Portals (BOI14_portals)	C++98	20 / 100	4 ms	24736 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], D[1001][1001], Dy[4]={0,1,0,-1}, Dx[4]={1,0,-1,0};
int Up[1001][1001], Down[1001][1001], Left[1001][1001], Right[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]=='S')
            {
                Sy=i;
                Sx=j;
            }
            else if(temp[j]=='C')
            {
                Cy=i;
                Cx=j;
            }
            else if(temp[j]=='#')
                A[i][j]=1;
            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
                Left[i][j]=x+1;
        }
        for(j=C+1 ; j>=0 ; j--)
        {
            if(A[i][j])
                x=j;
            else
                Right[i][j]=x-1;
        }
    }
    for(i=0 ; i<=C+1 ; i++)
    {
        for(j=0 ; j<=R+1 ; j++)
        {
            if(A[j][i])
                x=j;
            else
                Up[j][i]=x+1;
        }
        for(j=R+1 ; j>=0 ; j--)
        {
            if(A[j][i])
                x=j;
            else
                Down[j][i]=x-1;
        }
    }
}

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

    D[Sy][Sx]=0;
    q.push(Sy);
    q.push(Sx);
    while(!q.empty())
    {
        y=q.front();
        q.pop();
        x=q.front();
        q.pop();
        ok=0;
        for(i=0 ; i<4 ; i++)
        {
            ty=y+Dy[i];
            tx=x+Dx[i];
            if(A[ty][tx])
                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)
        {
            if(D[Up[y][x]][x]>D[y][x]+1)
            {
                D[Up[y][x]][x]=D[y][x]+1;
                q.push(Up[y][x]);
                q.push(x);
            }
            if(D[Down[y][x]][x]>D[y][x]+1)
            {
                D[Down[y][x]][x]=D[y][x]+1;
                q.push(Down[y][x]);
                q.push(x);
            }
            if(D[y][Left[y][x]]>D[y][x]+1)
            {
                D[y][Left[y][x]]=D[y][x]+1;
                q.push(y);
                q.push(Left[y][x]);
            }
            if(D[y][Right[y][x]]>D[y][x]+1)
            {
                D[y][Right[y][x]]=D[y][x]+1;
                q.push(y);
                q.push(Right[y][x]);
            }
        }
    }
}

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