| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 40561 |
2018-02-04T19:04:57 Z |
Hassoony |
Portal (COCI17_portal) |
C++14 |
|
156 ms |
79568 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=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=-1,l=-1,d=-1,r=-1;
for(int k=j-1;k>=1;k--){
if(a[i][k]=='#'){
l=k+1;
break;
}
}
for(int k=j+1;k<=m;k++){
if(a[i][k]=='#'){
r=k-1;
break;
}
}
for(int k=i-1;k>=1;k--){
if(a[k][j]=='#'){
u=k+1;
break;
}
}
for(int k=i+1;k<=n;k++){
if(a[k][j]=='#'){
d=k-1;
break;
}
}
if(u!=i&&u!=-1)v[getnode(i,j)].push_back({getnode(u,j),getmin(i-u,j-l+1,r-j+1,d-i+1)});
if(d!=i&&d!=1)v[getnode(i,j)].push_back({getnode(d,j),getmin(d-i,j-l+1,r-j+1,i-u+1)});
if(l!=i&&l!=-1)v[getnode(i,j)].push_back({getnode(i,l),getmin(j-l,i-u+1,d-i+1,r-j+1)});
if(r!=i&&r!=-1)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 (*)[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;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
14712 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
14848 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
14936 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
15036 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
15036 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
25 ms |
20820 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
43 ms |
28100 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
104 ms |
55088 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
132 ms |
67640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
156 ms |
79568 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
