Submission #41157

#	Time	Username	Problem	Language	Result	Execution time	Memory
41157		14kg	Portals (BOI14_portals)	C++11	100 / 100	920 ms	117716 KiB

portals

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#define N 1001
#define INF 1000000000

using namespace std;
typedef pair<int,pair<int,int> > pip;
int n, m, board[N][N], go[N][N], d[N][N];
int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};
bool go_check[N][N], check[N][N];
pair<int,int> S, E;
vector<pair<int,int> > p[N][N], O[1000001];
queue<int> Q;
queue<pip> PQ;

void bfs_go(){
    int ty, tx, yy, xx;
    bool w_check;

    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++){
            w_check=false;
            for(int s=0; s<4; s++){
                ty=i+dy[s], tx=j+dx[s];
                if(ty<1 || ty>n || tx<1 || tx>m) w_check=true;
                else if(board[ty][tx]) w_check=true;
            }
            if(w_check){
                go_check[i][j]=true, Q.push(i), Q.push(j);
            }
        }

    while(!Q.empty()){
        yy=Q.front(), Q.pop();
        xx=Q.front(), Q.pop();

        for(int i=0; i<4; i++){
            ty=yy+dy[i], tx=xx+dx[i];
            if(1<=ty && ty<=n && 1<=tx && tx<=m && go_check[ty][tx]==false && board[ty][tx]==0){
                go[ty][tx]=go[yy][xx]+1, go_check[ty][tx]=true;
                Q.push(ty), Q.push(tx);
            }
        }
    }
}
void Push(){
    pair<int,int> temp;

    for(int i=1; i<=n; i++){
        temp={i,1};
        for(int j=1; j<=m; j++){
            if(board[i][j]) temp={i,j+1};
            else p[i][j].push_back(temp);
        }
    }
    for(int i=1; i<=n; i++){
        temp={i,m};
        for(int j=m; j>=1; j--){
            if(board[i][j]) temp={i,j-1};
            else p[i][j].push_back(temp);
        }
    }
    for(int j=1; j<=m; j++){
        temp={1,j};
        for(int i=1; i<=n; i++){
            if(board[i][j]) temp={i+1,j};
            else p[i][j].push_back(temp);
        }
    }
    for(int j=1; j<=m; j++){
        temp={n,j};
        for(int i=n; i>=1; i--){
            if(board[i][j]) temp={i-1,j};
            else p[i][j].push_back(temp);
        }
    }
}
void PQ_push(int yy, int xx){
    int ty, tx;

    if(check[yy][xx]) return;
    check[yy][xx]=true;

    for(int i=0; i<4; i++){
        ty=yy+dy[i], tx=xx+dx[i];
        if(1<=ty && ty<=n && 1<=tx && tx<=m && d[ty][tx]>d[yy][xx]+1 && board[ty][tx]==0){
            d[ty][tx]=d[yy][xx]+1;
            PQ.push({d[ty][tx],{ty,tx}});
        }
    }
    for(vector<pair<int,int> >::iterator it=p[yy][xx].begin(); it!=p[yy][xx].end(); it++){
        ty=it->first, tx=it->second;
        if(d[ty][tx]>d[yy][xx]+go[yy][xx]+1){
            d[ty][tx]=d[yy][xx]+go[yy][xx]+1;
            O[d[ty][tx]].push_back({ty,tx});
        }
    }
}
int main(){
    char in[1005];

    scanf("%d %d",&n,&m);
    for(int i=1; i<=n; i++){
        scanf("%s",in+1);
        for(int j=1; j<=m; j++)
            if(in[j]=='#') board[i][j]=1;
            else if(in[j]=='S') S={i,j};
            else if(in[j]=='C') E={i,j};
    }

    bfs_go(), Push();
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) d[i][j]=INF;

    PQ.push({0,{S.first,S.second}}), d[S.first][S.second]=0;
    for(int k=0; !check[E.first][E.second]; k++){
        while(PQ.empty()==false && PQ.front().first==k){
            PQ_push(PQ.front().second.first,PQ.front().second.second), PQ.pop();
        }
        for(vector<pair<int,int> >::iterator it=O[k].begin(); it!=O[k].end(); it++){
            PQ_push(it->first,it->second);
        }
    }
    printf("%d",d[E.first][E.second]);
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:104:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&m);
                         ^
portals.cpp:106:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",in+1);
                         ^

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