Submission #1097263

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

portals

#include <bits/stdc++.h>
using namespace std;
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(){

    scanf("%d %d",&n,&m);

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

        scanf("%s",arr[i]);
        for(int j=1;j<=m;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=m; j>=1; 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=n;i>=1;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(){
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    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(been[x][y]==true)
            continue;
        if(arr[x][y]=='C'){
            printf("%d",w);
            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} });
    }
}

Compilation message (stderr)

portals.cpp: In function 'void input()':
portals.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
portals.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%s",arr[i]);
      |         ~~~~~^~~~~~~~~~~~~

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