#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;
/*if(z>t[deb][deb2])
{
q.pop();
continue;
}*/
q.pop();
int k=deb;
if(v[deb][deb2]!='#')
{
while(deb+1<n && v[deb+1][deb2]!='#')
{
deb++;
}
if(deb!=k && z+1<t[deb][deb2])
{
t[deb][deb2]=z+1;
q.push({{deb,deb2},{z+1,e+1}});
}
deb=k;
while(deb-1>=0 && v[deb-1][deb2]!='#')
{
//cout << deb << " " << deb2 << endl;
deb--;
}
if(deb!=k && z+1<t[deb][deb2])
{
t[deb][deb2]=z+1;
q.push({{deb,deb2},{z+1,e+1}});
}
k=deb2;
while(deb2+1<m && v[deb][deb2+1]!='#')
{
deb2++;
}
if(deb2!=k && z+1<t[deb][deb2])
{
t[deb][deb2]=z+1;
q.push({{deb,deb2},{z+1,e+1}});
}
deb2=k;
while(deb2!=k && deb2-1>=0 && v[deb][deb2-1]!='#')
{
deb2--;
}
if(z+1<t[deb][deb2])
{
t[deb][deb2]=z+1;
q.push({{deb,deb2},{z+1,e+1}});
}
}
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])
{
t[deb+elem][deb2+elem2]=z+1;
q.push({{deb+elem,deb2+elem2},{z+1,e}});
}
if(deb-elem>=0 && deb2-elem2>=0 && v[deb-elem][deb2-elem2]!='#' && z+1<t[deb-elem][deb2-elem2])
{
t[deb-elem][deb2-elem2]=z+1;
q.push({{deb-elem,deb2-elem2},{z+1,e}});
}
}
}
}
}
cout << t[xx][yy] << endl;
}
Compilation message
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:117:21: warning: 'yy' may be used uninitialized in this function [-Wmaybe-uninitialized]
117 | cout << t[xx][yy] << endl;
| ^
portals.cpp:117:17: warning: 'xx' may be used uninitialized in this function [-Wmaybe-uninitialized]
117 | cout << t[xx][yy] << endl;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
