Submission #1097252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097252		lomta	Portals (BOI14_portals)	C++17	0 / 100	810 ms	262144 KiB

portals

#include <bits/stdc++.h>

using namespace std;

#define ll long long

char arr[1003][1003];
bool been[1003][1003];
priority_queue<pair<int,pair<int,int> > > pq;
int dirx[4]={1,0,-1,0};
int diry[4]={0,1,0,-1};
int l[1003][1003],r[1003][1003],u[1003][1003],d[1003][1003];
int n,m;


bool check(int x,int y){

    if(x<1 || x>n || y<1 || y>m)
        return false;

    if(been[x][y]==true)
        return false;
    
    if(arr[x][y]=='#')
        return false;
    
    return true;

}
void input(){

    cin>>n>>m;

    for(int i=1;i<=n;i++){

        for(int j=1;j<=m;j++){

            cin>>arr[i][j];

            if(arr[i][j]=='S'){
                pq.push({0,{i,j}});
            }

        }
    }



}

void portals(){

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(arr[i][j]=='#'){
                l[i][j]=j+1;
            }
            else if(j==1){
                l[i][j]=1;
            }
            else{
                l[i][j]=l[i][j-1];
            }
        }
    }


    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(arr[i][j] == '#'){
                r[i][j] = j-1;
            }
            else if(j == m){
                r[i][j] = m;
            }
            else{
                r[i][j] = r[i][j+1];
            }
        }
    }


    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(arr[i][j]=='#'){
                u[i][j]=i+1;
            }
            else if(i==1){
                u[i][j]=1;
            }
            else{
                u[i][j]=u[i-1][j];
            }
        }
    }


    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(arr[i][j]=='#'){
                d[i][j]=i-1;
            }
            else if(i==n){
                d[i][j]=n;
            }
            else{
                d[i][j]=d[i+1][j];
            }
        }
    }

}
int main(){
    input();
    portals();

    while(!pq.empty()){

        int w=-pq.top().first;
        int x=pq.top().second.first;
        int y=pq.top().second.second;
        pq.pop();
        if(arr[x][y]=='C'){
            cout<<w<<endl;
            return 0;
        }
        been[x][y]=true;
        for(int i=0;i<4;i++){
            int nx=x+dirx[i];
            int ny=y+diry[i];

            if(check(nx,ny)==true){
                pq.push({-(w+1),{nx,ny}});
            }
        }

        int ds=min({abs(l[x][y]-y),abs(r[x][y]-y),abs(u[x][y]-x),abs(d[x][y]-x)});

        pq.push({-(ds+w+1), {x, l[x][y]} });
        pq.push({-(ds+w+1), {x, r[x][y]} });
        pq.push({-(ds+w+1), {u[x][y], y} });
        pq.push({-(ds+w+1), {d[x][y], y} });
    }
}

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