Submission #1097266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097266		lomta	Portals (BOI14_portals)	C++17	0 / 100	1 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",n);
    scanf("%d",m);

    for(int i=1;i<=n;i++){
        string s;
        scanf("%s",s);
        for(int j=1;j<=m;j++){

            arr[i][j]=s[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:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'int' [-Wformat=]
   28 |     scanf("%d",n);
      |            ~^  ~
      |             |  |
      |             |  int
      |             int*
portals.cpp:29:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'int' [-Wformat=]
   29 |     scanf("%d",m);
      |            ~^  ~
      |             |  |
      |             |  int
      |             int*
portals.cpp:33:17: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'std::string' {aka 'std::__cxx11::basic_string<char>'} [-Wformat=]
   33 |         scanf("%s",s);
      |                ~^   ~
      |                 |   |
      |                 |   std::string {aka std::__cxx11::basic_string<char>}
      |                 char*
portals.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf("%d",n);
      |     ~~~~~^~~~~~~~
portals.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     scanf("%d",m);
      |     ~~~~~^~~~~~~~
portals.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         scanf("%s",s);
      |         ~~~~~^~~~~~~~

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