Submission #10937

#	Time	Username	Problem	Language	Result	Execution time	Memory
10937		dohyun0324	Portals (BOI14_portals)	C++98	100 / 100	348 ms	37968 KiB

portals

#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
typedef pair<int,int> ppair;
priority_queue<ppair,vector<ppair>,greater<ppair> >arr;
char s[1010],a[1010][1010];
int n,m,p,r=-1,f=-1,ex,ey,sx,sy,dis[1010][1010],ch[1010][1010];
int left[1010][1010],right[1010][1010],down[1010][1010],up[1010][1010];
int xx[5]={0,1,0,-1,0};
int yy[5]={0,0,1,0,-1};
struct data
{
    int x,y,lev;
}q[1000010];
void bfs1()
{
    int i,kx,ky;
    while(f!=r)
    {
        f++;
        for(i=1;i<=4;i++)
        {
            kx=q[f].x+xx[i]; ky=q[f].y+yy[i];
            if(ch[kx][ky] || a[kx][ky]=='#' || a[kx][ky]==0) continue;
            ch[kx][ky]=1;
            r++; q[r].x=kx; q[r].y=ky; q[r].lev=q[f].lev+1; dis[kx][ky]=q[r].lev;
        }
    }
}
void bfs2()
{
    int i,j,x,y,lev,kx,ky;
    f=-1, r=0;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++) ch[i][j]=2147483647;
    }
    arr.push(make_pair(0,sx*(m+1)+sy)); ch[sx][sy]=0;
    while(arr.size())
    {
        x=arr.top().second/(m+1); y=arr.top().second%(m+1); lev=arr.top().first;
        arr.pop();
        if(x==ex && y==ey){printf("%d",lev); return;}
        for(i=1;i<=4;i++)
        {
            kx=x+xx[i]; ky=y+yy[i];
            if(ch[kx][ky]<=lev+1 || a[kx][ky]=='#' || a[kx][ky]==0) continue;
            ch[kx][ky]=lev+1;
            arr.push(make_pair(lev+1,kx*(m+1)+ky));
        }
        for(i=1;i<=4;i++)
        {
            if(i==1) kx=left[x][y]/(m+1), ky=left[x][y]%(m+1);
            if(i==2) kx=right[x][y]/(m+1), ky=right[x][y]%(m+1);
            if(i==3) kx=down[x][y]/(m+1), ky=down[x][y]%(m+1);
            if(i==4) kx=up[x][y]/(m+1), ky=up[x][y]%(m+1);
            if(ch[kx][ky]<=dis[x][y]+lev+1 || a[kx][ky]=='#' || a[kx][ky]==0) continue;
            ch[kx][ky]=dis[x][y]+lev+1;
            arr.push(make_pair(dis[x][y]+lev+1,kx*(m+1)+ky));
        }
    }
}
int main()
{
    int i,j;
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%s",s);
        for(j=1;j<=m;j++)
        {
            a[i][j]=s[j-1];
            if(a[i][j]=='C') ex=i, ey=j;
            if(a[i][j]=='S') sx=i, sy=j;
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(a[i-1][j]=='#' || a[i][j-1]=='#' || a[i+1][j]=='#' || a[i][j+1]=='#' || a[i-1][j]==0 || a[i][j-1]==0 || a[i+1][j]==0 || a[i][j+1]==0)
            {
                r++; q[r].x=i; q[r].y=j; ch[i][j]=1;
            }
        }
    }
    for(i=1;i<=n;i++)
    {
        p=0;
        for(j=1;j<=m;j++)
        {
            if(a[i][j]=='#') p=j;
            else left[i][j]=i*(m+1)+p+1;
        }
        p=m+1;
        for(j=m;j>=1;j--)
        {
            if(a[i][j]=='#') p=j;
            else right[i][j]=i*(m+1)+p-1;
        }
    }
    for(i=1;i<=m;i++)
    {
        p=0;
        for(j=1;j<=n;j++)
        {
            if(a[j][i]=='#') p=j;
            else up[j][i]=(p+1)*(m+1)+i;
        }
        p=n+1;
        for(j=n;j>=1;j--)
        {
            if(a[j][i]=='#') p=j;
            else down[j][i]=(p-1)*(m+1)+i;
        }
    }
    bfs1();
    bfs2();
    return 0;
}

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