Submission #40124

#	Time	Username	Problem	Language	Result	Execution time	Memory
40124		tiger13084	Portal (COCI17_portal)	C++14	120 / 120	76 ms	13948 KiB

portal

#include<stdio.h>
#include<queue>
#define inf 2e9
using namespace std;

int In[505][505],Wall[505][505],Sp[505][505];
deque< pair<int,int> > Q;
priority_queue< pair<int,pair<int,int> > > Pq;

struct xx{
    pair<int,int> up,dn,lf,ri;
}Por[505][505];

pair<int,pair<int,int> > make_triple(int a,int b,int c){
    pair<int,pair<int,int> > temp;
    temp.first=a;
    temp.second.first=b;
    temp.second.second=c;
    return temp;
}

void Op(int x,int y,int tempx,int tempy,int tempdis){
    if(In[tempx][tempy]!='#'&&Sp[tempx][tempy]>Sp[x][y]+tempdis){
        Sp[tempx][tempy]=Sp[x][y]+tempdis;
        Pq.push(make_triple(-Sp[tempx][tempy],tempx,tempy));
    }
}

main(){
    int n,m;
    pair<int,int> ed;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf(" %c",&In[i][j]);
            if(In[i][j]=='#')
                Q.push_back(make_pair(i,j));
            else
                Wall[i][j]=inf;
            if(In[i][j]=='C')
                Pq.push(make_triple(0,i,j));
            else
                Sp[i][j]=inf;
            if(In[i][j]=='F')
                ed=make_pair(i,j);
        }
    }
    for(int i=1;i<=n;i++){
        int temp1=1;
        for(int j=1;j<=m;j++){
            if(In[i][j]=='#'){
                temp1=j+1;
                continue;
            }
            Por[i][j].lf=make_pair(i,temp1);
        }
        int temp2=m;
        for(int j=m;j>=1;j--){
            if(In[i][j]=='#'){
                temp2=j-1;
                continue;
            }
            Por[i][j].ri=make_pair(i,temp2);
        }
    }
    for(int j=1;j<=m;j++){
        int temp1=1;
        for(int i=1;i<=n;i++){
            if(In[i][j]=='#'){
                temp1=i+1;
                continue;
            }
            Por[i][j].up=make_pair(temp1,j);
        }
        int temp2=n;
        for(int i=n;i>=1;i--){
            if(In[i][j]=='#'){
                temp2=i-1;
                continue;
            }
            Por[i][j].dn=make_pair(temp2,j);
        }
    }
    while(!Q.empty()){
        int x=Q.front().first;
        int y=Q.front().second;
        Q.pop_front();
        if(Wall[x+1][y]==inf){
            Wall[x+1][y]=Wall[x][y]+1;
            Q.push_back(make_pair(x+1,y));
        }
        if(Wall[x-1][y]==inf){
            Wall[x-1][y]=Wall[x][y]+1;
            Q.push_back(make_pair(x-1,y));
        }
        if(Wall[x][y+1]==inf){
            Wall[x][y+1]=Wall[x][y]+1;
            Q.push_back(make_pair(x,y+1));
        }
        if(Wall[x][y-1]==inf){
            Wall[x][y-1]=Wall[x][y]+1;
            Q.push_back(make_pair(x,y-1));
        }
    }
    int tempx,tempy,tempdis;
    while(!Pq.empty()){
        int dis=-Pq.top().first;
        int x=Pq.top().second.first;
        int y=Pq.top().second.second;
        Pq.pop();
        if(dis!=Sp[x][y])
            continue;
        Op(x,y,x+1,y,1);
        Op(x,y,x-1,y,1);
        Op(x,y,x,y+1,1);
        Op(x,y,x,y-1,1);
        Op(x,y,Por[x][y].up.first,Por[x][y].up.second,Wall[x][y]);
        Op(x,y,Por[x][y].dn.first,Por[x][y].dn.second,Wall[x][y]);
        Op(x,y,Por[x][y].lf.first,Por[x][y].lf.second,Wall[x][y]);
        Op(x,y,Por[x][y].ri.first,Por[x][y].ri.second,Wall[x][y]);
    }
    if(Sp[ed.first][ed.second]!=inf)
        printf("%d",Sp[ed.first][ed.second]);
    else
        printf("nemoguce");
//    printf("\n\n");
//    for(int i=1;i<=n;i++){
//        for(int j=1;j<=m;j++){
//            if(Sp[i][j]==inf)
//                printf("- ");
//            else printf("%d ",Sp[i][j]);
//        }
//        printf("\n");
//    }
//    printf("\n\n");
//    for(int i=1;i<=n;i++){
//        for(int j=1;j<=m;j++)
//            printf("%d ",Wall[i][j]);
//        printf("\n");
//    }
}

Compilation message (stderr)

portal.cpp:29:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
portal.cpp: In function 'int main()':
portal.cpp:35:34: warning: format '%c' expects argument of type 'char*', but argument 2 has type 'int*' [-Wformat=]
             scanf(" %c",&In[i][j]);
                                  ^
portal.cpp:105:9: warning: unused variable 'tempx' [-Wunused-variable]
     int tempx,tempy,tempdis;
         ^
portal.cpp:105:15: warning: unused variable 'tempy' [-Wunused-variable]
     int tempx,tempy,tempdis;
               ^
portal.cpp:105:21: warning: unused variable 'tempdis' [-Wunused-variable]
     int tempx,tempy,tempdis;
                     ^
portal.cpp:32:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
                        ^
portal.cpp:35:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c",&In[i][j]);
                                   ^

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12