Submission #40558

#TimeUsernameProblemLanguageResultExecution timeMemory
40558HassoonyPortal (COCI17_portal)C++14
72 / 120
183 ms30376 KiB
#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=509; int n,m,dis[MX*MX],vis[MX*MX]; char a[MX][MX]; bool b=0; vector<pair<int,int> >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,l,d,r; 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!=i)v[getnode(i,j)].push_back({getnode(i,l),getmin(j-l,i-u+1,d-i+1,r-j+1)}); if(r!=i)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<int,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,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:36:44: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[509]' [-Wformat=]
     for(int i=1;i<=n;i++)scanf("%s",&a[i]+1);
                                            ^
portal.cpp:36: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:75:9: warning: 'x1' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int x1,x2;
         ^
portal.cpp:75:12: warning: 'x2' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int x1,x2;
            ^
portal.cpp:13:21: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return ((x<<9)|y);
                     ^
portal.cpp:44:23: note: 'r' was declared here
             int u,l,d,r;
                       ^
portal.cpp:13:15: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return ((x<<9)|y);
               ^
portal.cpp:44:21: note: 'd' was declared here
             int u,l,d,r;
                     ^
portal.cpp:13:21: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return ((x<<9)|y);
                     ^
portal.cpp:44:19: note: 'l' was declared here
             int u,l,d,r;
                   ^
portal.cpp:13:15: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return ((x<<9)|y);
               ^
portal.cpp:44:17: note: 'u' was declared here
             int u,l,d,r;
                 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...