Submission #40562

#	Time	Username	Problem	Language	Result	Execution time	Memory
40562		Hassoony	Portal (COCI17_portal)	C++14	120 / 120	212 ms	43536 KiB

portal

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef long long ll;
const ll inf=(1ll<<60);
const ll mod=1e9+7;
const int MX=550;
int n,m,vis[MX*MX];
ll dis[MX*MX];
char a[MX][MX];
bool b=0;
vector<pair<int,ll> >v[MX*MX];
int getnode(int x,int y){
    return ((x<<9)|y);
}
int getmin(int x1,int x2,int x3,int x4){
    return min(x1,min(x2,min(x3,x4)));
}
void dfs(int x,int y){
    if(vis[x])return;
    if(x==y){
        b=1;
        return;
    }
    vis[x]=1;
    for(auto pp:v[x]){
        dfs(pp.first,y);
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=m+1;j++){
            a[i][j]='#';
        }
    }
    for(int i=1;i<=n;i++)scanf("%s",&a[i]+1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]=='#')continue;
            v[getnode(i,j)].push_back({getnode(i-1,j),1});
            v[getnode(i,j)].push_back({getnode(i+1,j),1});
            v[getnode(i,j)].push_back({getnode(i,j-1),1});
            v[getnode(i,j)].push_back({getnode(i,j+1),1});
            int u=i+1,l=j-1,d=i-1,r=j+1;
            for(int k=j-1;k>=0;k--){
                if(a[i][k]=='#'){
                    l=k+1;
                    break;
                }
            }
            for(int k=j+1;k<=m+1;k++){
                if(a[i][k]=='#'){
                    r=k-1;
                    break;
                }
            }
            for(int k=i-1;k>=0;k--){
                if(a[k][j]=='#'){
                    u=k+1;
                    break;
                }
            }
            for(int k=i+1;k<=n+1;k++){
                if(a[k][j]=='#'){
                    d=k-1;
                    break;
                }
            }
            if(u!=i)v[getnode(i,j)].push_back({getnode(u,j),getmin(i-u,j-l+1,r-j+1,d-i+1)});
            if(d!=i)v[getnode(i,j)].push_back({getnode(d,j),getmin(d-i,j-l+1,r-j+1,i-u+1)});
            if(l!=j)v[getnode(i,j)].push_back({getnode(i,l),getmin(j-l,i-u+1,d-i+1,r-j+1)});
            if(r!=j)v[getnode(i,j)].push_back({getnode(i,r),getmin(r-j,i-u+1,d-i+1,j-l+1)});
        }
    }
    int x1,x2;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]=='C')x1=getnode(i,j);
            if(a[i][j]=='F')x2=getnode(i,j);
        }
    }
    dfs(x1,x2);
    if(!b){
        puts("nemoguce");
        return 0;
    }
    priority_queue<pair<ll,int> >pq;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dis[getnode(i,j)]=1e8;
            vis[getnode(i,j)]=0;
        }
    }
    dis[x1]=0;
    pq.push({0,x1});
    while(!pq.empty()){
        int x=pq.top().second;
        ll c=-pq.top().first;pq.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(auto pp:v[x]){
            if(pp.second+c<dis[pp.first]){
                dis[pp.first]=pp.second+c;
                pq.push({-dis[pp.first],pp.first});
            }
        }
    }
    cout<<dis[x2]<<endl;
}

Compilation message (stderr)

portal.cpp: In function 'int main()':
portal.cpp:37:44: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[550]' [-Wformat=]
     for(int i=1;i<=n;i++)scanf("%s",&a[i]+1);
                                            ^
portal.cpp:37:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++)scanf("%s",&a[i]+1);
                                             ^
portal.cpp:76:9: warning: 'x1' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int x1,x2;
         ^
portal.cpp:76:12: warning: 'x2' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int x1,x2;
            ^

• 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