| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 40558 |
2018-02-04T19:00:46 Z |
Hassoony |
Portal (COCI17_portal) |
C++14 |
|
183 ms |
30376 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,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
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 time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
6392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
6628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
6628 KB |
Output is correct |
| 2 |
Correct |
6 ms |
6628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
6656 KB |
Output is correct |
| 2 |
Correct |
6 ms |
6656 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
6748 KB |
Output is correct |
| 2 |
Correct |
6 ms |
6880 KB |
Output is correct |
| 3 |
Correct |
6 ms |
6880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
9084 KB |
Output is correct |
| 2 |
Correct |
11 ms |
9084 KB |
Output is correct |
| 3 |
Correct |
18 ms |
9084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
11404 KB |
Output is correct |
| 2 |
Correct |
11 ms |
11404 KB |
Output is correct |
| 3 |
Incorrect |
24 ms |
11404 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
122 ms |
21012 KB |
Output is correct |
| 2 |
Correct |
70 ms |
21012 KB |
Output is correct |
| 3 |
Incorrect |
68 ms |
21012 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
155 ms |
25256 KB |
Output is correct |
| 2 |
Correct |
49 ms |
25256 KB |
Output is correct |
| 3 |
Incorrect |
110 ms |
25256 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
183 ms |
30376 KB |
Output is correct |
| 2 |
Correct |
52 ms |
30376 KB |
Output is correct |
| 3 |
Incorrect |
152 ms |
30376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
