Submission #14816

#	Time	Username	Problem	Language	Result	Execution time	Memory
14816		eaststar	Portals (BOI14_portals)	C++98	100 / 100	179 ms	146164 KiB

portals

#include <stdio.h>
#include <algorithm>
using namespace std;
struct Q{
    int r,c,d;
    Q(){}
    Q(int r,int c,int d):r(r),c(c),d(d){}
    bool operator<(const Q&r)const{
        return d>r.d;
    }
}q[10000010];
int a[1010][1010],n,m,sr,sc,er,ec;
int b[1010][1010][4],dis[1010][1010],t[1010][1010];
int x[]={-1,0,1,0},y[]={0,1,0,-1};
void BFS(){
    int i,j,r,c,d,nr,nc,p=1;
    for(i=1;i<=n;++i){
        for(j=1;j<=m;++j)dis[i][j]=1e7;
    }
    dis[sr][sc]=0;
    q[0]=Q(sr,sc,0);
    while(p){
        r=q[0].r,c=q[0].c,d=q[0].d;
        if(r==er&&c==ec)break;
        pop_heap(q,q+p);
        --p;
        for(i=0;i<4;++i){
            nr=r+x[i],nc=c+y[i];
            if(a[nr][nc]||dis[nr][nc]<=d+1)continue;
            q[p++]=Q(nr,nc,d+1);
            push_heap(q,q+p);
            dis[nr][nc]=d+1;
        }
        for(i=0;i<4;++i){
            if(i%2)nr=r,nc=b[r][c][i];
            else nr=b[r][c][i],nc=c;
            if(dis[nr][nc]<=d+t[r][c]+1)continue;
            q[p++]=Q(nr,nc,d+t[r][c]+1);
            push_heap(q,q+p);
            dis[nr][nc]=d+t[r][c]+1;
        }
    }
    printf("%d",q[0].d);
}
void portal(){
    int i,j,k,l;
    for(i=1;i<=n;++i){
        for(j=1;j<=m;++j)if(!a[i][j]){
            if(a[i][j-1])l=j;
            if(a[i][j+1])for(k=l;k<=j;++k)b[i][k][1]=j,b[i][k][3]=l,t[i][k]=min(k-l,j-k);
        }
    }
    for(i=1;i<=m;++i){
        for(j=1;j<=n;++j)if(!a[j][i]){
            if(a[j-1][i])l=j;
            if(a[j+1][i])for(k=l;k<=j;++k)b[k][i][0]=l,b[k][i][2]=j,t[k][i]=min(min(k-l,j-k),t[k][i]);
        }
    }
}
void input(){
    int i,j;
    char c[1010];
    scanf("%d%d",&n,&m);
    for(i=0;i<=n+1;++i)a[i][0]=a[i][m+1]=1;
    for(i=1;i<=m;++i)a[0][i]=a[n+1][i]=1;
    for(i=1;i<=n;++i){
        scanf("%s",c+1);
        for(j=1;j<=m;++j){
            if(c[j]=='S')sr=i,sc=j;
            if(c[j]=='C')er=i,ec=j;
            if(c[j]=='#')a[i][j]=1;
        }
    }
}
int main(){
    input();
    portal();
    BFS();
    return 0;
}

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