| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 40559 |
2018-02-04T19:03:11 Z |
Hassoony |
Portal (COCI17_portal) |
C++14 |
|
221 ms |
42424 KB |
#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,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,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<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
portal.cpp: In function 'int main()':
portal.cpp:37: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: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;
^
portal.cpp:14:21: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
return ((x<<9)|y);
^
portal.cpp:45:23: note: 'r' was declared here
int u,l,d,r;
^
portal.cpp:14:15: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
return ((x<<9)|y);
^
portal.cpp:45:21: note: 'd' was declared here
int u,l,d,r;
^
portal.cpp:14:21: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
return ((x<<9)|y);
^
portal.cpp:45:19: note: 'l' was declared here
int u,l,d,r;
^
portal.cpp:14:15: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
return ((x<<9)|y);
^
portal.cpp:45:17: note: 'u' was declared here
int u,l,d,r;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
6392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
6624 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
6676 KB |
Output is correct |
| 2 |
Correct |
6 ms |
6676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
6788 KB |
Output is correct |
| 2 |
Correct |
6 ms |
6788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
6788 KB |
Output is correct |
| 2 |
Correct |
6 ms |
6788 KB |
Output is correct |
| 3 |
Correct |
6 ms |
6788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
10460 KB |
Output is correct |
| 2 |
Correct |
11 ms |
10460 KB |
Output is correct |
| 3 |
Correct |
20 ms |
10460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
14124 KB |
Output is correct |
| 2 |
Correct |
15 ms |
14124 KB |
Output is correct |
| 3 |
Incorrect |
25 ms |
14124 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
136 ms |
28688 KB |
Output is correct |
| 2 |
Correct |
78 ms |
28688 KB |
Output is correct |
| 3 |
Incorrect |
67 ms |
28688 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
178 ms |
35436 KB |
Output is correct |
| 2 |
Correct |
59 ms |
35436 KB |
Output is correct |
| 3 |
Incorrect |
110 ms |
35436 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
221 ms |
42424 KB |
Output is correct |
| 2 |
Correct |
61 ms |
42424 KB |
Output is correct |
| 3 |
Incorrect |
199 ms |
42424 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
