oj.uz

답안 #6153

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
6153 2014-06-21T07:01:32 Z baneling100 포탈들 (BOI14_portals) C++
20 / 100
 4 ms 40460 KB 
#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.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 40460 KB Output is correct
2 Correct 0 ms 40460 KB Output is correct
3 Correct 0 ms 40460 KB Output is correct
4 Correct 0 ms 40460 KB Output is correct
5 Correct 0 ms 40460 KB Output is correct
6 Correct 0 ms 40460 KB Output is correct
7 Correct 0 ms 40460 KB Output is correct
8 Correct 0 ms 40460 KB Output is correct
9 Correct 0 ms 40460 KB Output is correct
10 Incorrect 0 ms 40460 KB Output isn't correct

Subtask #2
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 40460 KB Output is correct
2 Correct 0 ms 40460 KB Output is correct
3 Correct 0 ms 40460 KB Output is correct
4 Correct 0 ms 40460 KB Output is correct
5 Correct 0 ms 40460 KB Output is correct
6 Correct 0 ms 40460 KB Output is correct
7 Correct 0 ms 40460 KB Output is correct
8 Correct 0 ms 40460 KB Output is correct
9 Correct 0 ms 40460 KB Output is correct
10 Incorrect 0 ms 40460 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 40460 KB Output is correct
2 Correct 0 ms 40460 KB Output is correct
3 Correct 0 ms 40460 KB Output is correct
4 Correct 0 ms 40460 KB Output is correct
5 Correct 4 ms 40460 KB Output is correct
6 Correct 4 ms 40460 KB Output is correct
7 Correct 0 ms 40460 KB Output is correct
8 Correct 0 ms 40460 KB Output is correct

Subtask #4
0.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 40460 KB Output is correct
2 Correct 0 ms 40460 KB Output is correct
3 Correct 0 ms 40460 KB Output is correct
4 Correct 0 ms 40460 KB Output is correct
5 Correct 0 ms 40460 KB Output is correct
6 Correct 0 ms 40460 KB Output is correct
7 Correct 0 ms 40460 KB Output is correct
8 Correct 0 ms 40460 KB Output is correct
9 Correct 0 ms 40460 KB Output is correct
10 Incorrect 0 ms 40460 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 40460 KB Output is correct
2 Correct 0 ms 40460 KB Output is correct
3 Correct 0 ms 40460 KB Output is correct
4 Correct 0 ms 40460 KB Output is correct
5 Correct 0 ms 40460 KB Output is correct
6 Correct 0 ms 40460 KB Output is correct
7 Correct 0 ms 40460 KB Output is correct
8 Correct 0 ms 40460 KB Output is correct
9 Correct 0 ms 40460 KB Output is correct
10 Incorrect 0 ms 40460 KB Output isn't correct
11 Halted 0 ms 0 KB -