Submission #465763

#TimeUsernameProblemLanguageResultExecution timeMemory
465763habibaissaPortals (BOI14_portals)C++17
0 / 100
1097 ms249732 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int32_t main() { int n,m; cin >> n >> m; int x,y,xx,yy; vector<vector<int> > v; v.resize(n); for(int i=0; i<n; i++) { for(int k=0; k<m; k++) { char p; cin >> p; if(p=='S') { x=i;y=k; } if(p=='C') { xx=i;yy=k; v[i].push_back('.'); continue; } v[i].push_back(p); } } vector<vector<int>> t; vector<int> poss; poss.push_back(1); poss.push_back(0); t.resize(n+5); for(int i=0;i<t.size();i++) t[i].resize(m+5,INT_MAX); queue<pair<pair<int,int>,pair<int,int> > > q; q.push(make_pair(make_pair(x,y),make_pair(0,0))); while(!q.empty()) { int deb=q.front().first.first; int deb2=q.front().first.second; int z=q.front().second.first; int e=q.front().second.second; t[deb][deb2]=min(z,t[deb][deb2]); //cout << deb << " " << deb2 << " " << t[deb][deb2] << '\n'; //cout << deb << " " << deb2 << " " << t[deb][deb2] << '\n'; if(deb==xx && deb2==yy) { q.pop(); continue; } q.pop(); for(int elem:poss) { for(int elem2:poss) { if(elem!=elem2) { if(deb+elem<n && deb2+elem2<m && v[deb+elem][deb2+elem2]!='#' && z+1<t[deb+elem][deb2+elem2]) { q.push({{deb+elem,deb2+elem2},{z+1,0}}); } if(deb-elem>=0 && deb2-elem2>=0 && v[deb-elem][deb2-elem2]!='#' && z+1<t[deb-elem][deb2-elem2]) { q.push({{deb-elem,deb2-elem2},{z+1,0}}); } } } } if(e==0) { int k=deb; if(deb-1==-1 || v[deb-1][deb2]=='#') { while( (deb+1<n && v[deb+1][deb2]!='#')) { deb++; } if(deb!=k && z+1<t[deb][deb2]) { q.push({{deb,deb2},{z+1,1}}); } }deb=k; if(deb+1==n || v[deb+1][deb2]=='#') { while( (deb-1>=0 && v[deb-1][deb2]!='#')) { //cout << deb << " " << deb2 << endl; deb--; } if(deb!=k && z+1<t[deb][deb2]) { q.push({{deb,deb2},{z+1,1}}); } } deb=k; k=deb2; if(deb2-1==-1 || v[deb][deb2-1]=='#') { while((deb2+1<m && v[deb][deb2+1]!='#')) { deb2++; } if(deb2!=k && z+1<t[deb][deb2]) { q.push({{deb,deb2},{z+1,1}}); } }deb2=k; if(deb2+1==m || v[deb][deb2+1]=='#') { while( (deb2-1>=0 && v[deb][deb2-1]!='#')) { deb2--; } if(deb2!=k && z+1<t[deb][deb2]) { q.push({{deb,deb2},{z+1,1}}); } } } else {int k=deb; while(deb+1<n && v[deb+1][deb2]!='#') { deb++; } if(deb!=k && z+1<t[deb][deb2]) { q.push({{deb,deb2},{z+1,1}}); } deb=k; while(deb-1>=0 && v[deb-1][deb2]!='#') { //cout << deb << " " << deb2 << endl; deb--; } if(deb!=k && z+1<t[deb][deb2]) { q.push({{deb,deb2},{z+1,1}}); } deb=k; k=deb2; while(deb2+1<m && v[deb][deb2+1]!='#') { deb2++; } if(deb2!=k && z+1<t[deb][deb2]) { q.push({{deb,deb2},{z+1,1}}); } deb2=k; while(deb2-1>=0 && v[deb][deb2-1]!='#') { deb2--; } if(deb2!=k && z+1<t[deb][deb2]) { q.push({{deb,deb2},{z+1,1}}); } } } cout << t[xx][yy] << endl; }

Compilation message (stderr)

portals.cpp: In function 'int32_t main()':
portals.cpp:36:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0;i<t.size();i++)
      |                 ~^~~~~~~~~
portals.cpp:171:21: warning: 'yy' may be used uninitialized in this function [-Wmaybe-uninitialized]
  171 |     cout << t[xx][yy] << endl;
      |                     ^
portals.cpp:171:17: warning: 'xx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  171 |     cout << t[xx][yy] << endl;
      |                 ^
#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...