Submission #16842

#	Time	Username	Problem	Language	Result	Execution time	Memory
16842		kdh9949	Portals (BOI14_portals)	C++98	70 / 100	1000 ms	40568 KiB

portals

#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
 
struct mindol{int x,y,t;bool operator<(const mindol &a)const{return t>a.t;}};
priority_queue<mindol> pq;
 
char m[1010][1010];
int dt[4][1010][1010],dist[1010][1010];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int w,h,gx,gy,flag;
 
int main(){
    scanf("%d%d",&w,&h);
    for(int i=1;i<=w;i++){
        scanf("%s",m[i]+1);
    }
    for(int i=0;i<=w+1;i++)for(int j=0;j<4;j++)m[i][0]=m[i][h+1]='#',dt[j][i][0]=dt[j][i][h+1]=-1;
    for(int i=0;i<=h+1;i++)for(int j=0;j<4;j++)m[0][i]=m[w+1][i]='#',dt[j][0][i]=dt[j][w+1][i]=-1;
    for(int i=1;i<=w;i++){
        for(int j=1;j<=h;j++){
            dist[i][j]=987654321;
            if(m[i][j]=='S')pq.push({i,j,0});
            if(m[i][j]=='C')gx=i,gy=j;
            dt[0][w+1-i][j]=( m[w+1-i][j]=='#' ? -1 :dt[0][w+2-i][j]+1);
            dt[1][i][j]=(m[i][j]=='#' ? -1 : dt[1][i-1][j]+1);
            dt[2][i][h+1-j]=(m[i][h+1-j]=='#' ? -1 : dt[2][i][h+2-j]+1);
            dt[3][i][j]=(m[i][j]=='#' ? -1 : dt[3][i][j-1]+1);
        }
    }
    mindol cur;
    while(!pq.empty()){
        cur=pq.top();
        pq.pop();
        if(m[cur.x][cur.y]=='#')continue;
        if(dist[cur.x][cur.y]<=cur.t)continue;
        dist[cur.x][cur.y]=cur.t;
        for(int i=0;i<4;i++){
            pq.push({cur.x+dx[i],cur.y+dy[i],cur.t+1});
        }
        for(int j=0;j<4;j++){
            if(dt[j][cur.x][cur.y]<=1)continue;
            if(cur.t+min(min(j==0?987654321:dt[0][cur.x][cur.y],j==1?987654321:dt[1][cur.x][cur.y]),
                         min(j==2?987654321:dt[2][cur.x][cur.y],j==3?987654321:dt[3][cur.x][cur.y]))+1>=
               dist[cur.x+dx[j]*dt[j][cur.x][cur.y]][cur.y+dy[j]*dt[j][cur.x][cur.y]])continue;
            pq.push({cur.x+dx[j]*dt[j][cur.x][cur.y],cur.y+dy[j]*dt[j][cur.x][cur.y],cur.t+min(min(j==0?987654321:dt[0][cur.x][cur.y],
                                                                                                  j==1?987654321:dt[1][cur.x][cur.y]),
                                                                                              min(j==2?987654321:dt[2][cur.x][cur.y],
                                                                                                  j==3?987654321:dt[3][cur.x][cur.y]))+1});
        }
    }
    printf("%d",dist[gx][gy]);
}

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