Submission #129896

#	Time	Username	Problem	Language	Result	Execution time	Memory
129896		Vardanyan	Portals (BOI14_portals)	C++14	100 / 100	369 ms	38172 KiB

portals

#include <bits/stdc++.h>
using namespace std;
 
const int N = 1005;
char a[N][N];
pair<int,int> lft[N][N];
pair<int,int> rg[N][N];
pair<int,int> up[N][N];
pair<int,int> dwn[N][N];
int d[N][N];
bool col[N][N];
int n,m;
bool check(int i,int j){
    if(a[i-1][j] == '#' || i-1 == 0) return true;
    if(a[i+1][j] == '#' || i+1 == n+1) return true;
    if(a[i][j+1] == '#' || j+1 == m+1) return true;
    if(a[i][j-1] == '#' || j-1 == 0) return true;
    return false;
}
int dist(int i1,int j1,int i2,int j2){
    return abs(i1-i2)+abs(j1-j2);
}
int main(){
    ios_base::sync_with_stdio(false);
 
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++) cin>>a[i][j];
    }
    int si,sj;
    int fi,fj;
    for(int i = 1;i<=n;i++){
        pair<int,int> now;
        now = {i,1};
        for(int j = 1;j<=m;j++){
            if(a[i][j] == '#'){
                now.second = j+1;
                continue;
            }
            if(a[i][j] == 'S'){
                si = i;
                sj = j;
            }
            if(a[i][j] == 'C'){
                fi = i;
                fj = j;
            }
            lft[i][j] = now;
        }
        now = {i,m};
        for(int j = m;j>=1;j--){
            if(a[i][j] == '#'){
                now.second = j-1;
                continue;
            }
            rg[i][j] = now;
        }
    }
    for(int j = 1;j<=m;j++){
        pair<int,int> now;
        now = {1,j};
        for(int i = 1;i<=n;i++){
            if(a[i][j] == '#'){
                now.first = i+1;
                continue;
            }
            up[i][j] = now;
        }
        now = {n,j};
        for(int i = n;i>=1;i--){
            if(a[i][j] == '#'){
                now.first = i-1;
                continue;
            }
            dwn[i][j] = now;
        }
    }
    /*for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            cout<<i<<" "<<j<<" "<<lft[i][j].first<<" "<<lft[i][j].second<<endl;
        }
    }*/
    priority_queue<pair<int,pair<int,int> > > pq;
    pq.push({0,{si,sj}});
    memset(d,63,sizeof(d));
    d[si][sj] = 0;
    while(!pq.empty()){
        pair<int,pair<int,int> > x = pq.top();
        pq.pop();
        int ds = x.first;
        int i = x.second.first;
        int j = x.second.second;
        if(i+1<=n && a[i+1][j]!='#' && d[i][j]+1<d[i+1][j]){
            d[i+1][j] = min(d[i+1][j],d[i][j]+1);
            pq.push({-d[i+1][j],{i+1,j}});
        }
        if(j+1<=m && a[i][j+1]!='#' && d[i][j]+1<d[i][j+1]){
            d[i][j+1] = min(d[i][j+1],d[i][j]+1);
            pq.push({-d[i][j+1],{i,j+1}});
        }
        if(i-1>=1 && a[i-1][j]!='#' && d[i][j]+1<d[i-1][j]){
            d[i-1][j] = min(d[i-1][j],d[i][j]+1);
            pq.push({-d[i-1][j],{i-1,j}});
        }
        if(j-1>=1 && a[i][j-1]!='#' && d[i][j]+1<d[i][j-1]){
            d[i][j-1] = min(d[i][j-1],d[i][j]+1);
            pq.push({-d[i][j-1],{i,j-1}});
        }
        int ii = lft[i][j].first;
        int jj = lft[i][j].second;
        int mot = dist(i,j,lft[i][j].first,lft[i][j].second);
        mot = min(mot,dist(i,j,rg[i][j].first,rg[i][j].second));
        mot = min(mot,dist(i,j,up[i][j].first,up[i][j].second));
        mot = min(mot,dist(i,j,dwn[i][j].first,dwn[i][j].second));
        mot++;
        if(ii && jj && d[i][j]+mot<d[ii][jj]){
            d[ii][jj] = d[i][j]+mot;
            pq.push({-d[ii][jj],{ii,jj}});
        }
        ii = rg[i][j].first;
        jj = rg[i][j].second;
        if(ii && jj && d[i][j]+mot<d[ii][jj]){
            d[ii][jj] = d[i][j]+mot;
            pq.push({-d[ii][jj],{ii,jj}});
        }
        ii = up[i][j].first;
        jj = up[i][j].second;
        if(ii && jj && d[i][j]+mot<d[ii][jj]){
            d[ii][jj] = d[i][j]+mot;
            pq.push({-d[ii][jj],{ii,jj}});
        }
        ii = dwn[i][j].first;
        jj = dwn[i][j].second;
        if(ii && jj && d[i][j]+mot<d[ii][jj]){
            d[ii][jj] = d[i][j]+mot;
            pq.push({-d[ii][jj],{ii,jj}});
        }
    }
    cout<<d[fi][fj]<<endl;
    return 0;
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:90:13: warning: unused variable 'ds' [-Wunused-variable]
         int ds = x.first;
             ^~
portals.cpp:86:15: warning: 'sj' may be used uninitialized in this function [-Wmaybe-uninitialized]
     d[si][sj] = 0;
     ~~~~~~~~~~^~~
portals.cpp:86:15: warning: 'si' may be used uninitialized in this function [-Wmaybe-uninitialized]
portals.cpp:139:19: warning: 'fj' may be used uninitialized in this function [-Wmaybe-uninitialized]
     cout<<d[fi][fj]<<endl;
                   ^
portals.cpp:139:19: warning: 'fi' may be used uninitialized in this function [-Wmaybe-uninitialized]

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