This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define INF INT_MAX
#define output for(int i=0;i<sizex;i++) { for(int j=0;j<sizey;j++) { cout << moveChart[i][j] << " "; }cout<<endl; }cout<<endl;
struct el{
int x, y, px, py, m;
el(){}
el( int _x, int _y ){ x = _x; y = _y; }
el( int _x, int _y, int _px, int _py, int _m ){ x = _x; y = _y; px = _px; py = _py; m = _m; }
};
const int maxN = 51;
int N, M;
char mat[maxN][maxN];
bool visited[maxN][maxN][maxN][maxN];
el startPos, endPos;
vector <el> portalPos[maxN][maxN];
int res;
queue <el> q;
bool isValid( int x, int y ){
return x >= 0 && x < N && y >= 0 && y < M;
}
bool wall( int x, int y ){
return x == -1 || y == -1 || x == N || y == M || mat[x][y] == '#';
}
void traverse( int Vx, int Vy, int px, int py, int m ){
int x, y;
x = Vx+1; y = Vy; if( !wall( x, y ) && !visited[x][y][px][py] ) q.push( el( x, y, px, py, m+1 ) );
x = Vx-1; y = Vy; if( !wall( x, y ) && !visited[x][y][px][py] ) q.push( el( x, y, px, py, m+1 ) );
x = Vx; y = Vy+1; if( !wall( x, y ) && !visited[x][y][px][py] ) q.push( el( x, y, px, py, m+1 ) );
x = Vx; y = Vy-1; if( !wall( x, y ) && !visited[x][y][px][py] ) q.push( el( x, y, px, py, m+1 ) );
if( px == N ) return;
x = Vx+1; y = Vy; if( wall( x, y ) && !visited[px][py][px][py] ) q.push( el( px, py, px, py, m+1 ) );
x = Vx-1; y = Vy; if( wall( x, y ) && !visited[px][py][px][py] ) q.push( el( px, py, px, py, m+1 ) );
x = Vx; y = Vy+1; if( wall( x, y ) && !visited[px][py][px][py] ) q.push( el( px, py, px, py, m+1 ) );
x = Vx; y = Vy-1; if( wall( x, y ) && !visited[px][py][px][py] ) q.push( el( px, py, px, py, m+1 ) );
}
void bfs( el V ){
while( !q.empty() ) q.pop();
q.push(V);
while( !q.empty() ){
V = q.front();
q.pop();
if( visited[V.x][V.y][V.px][V.py] ) continue;
visited[V.x][V.y][V.px][V.py] = true;
// cout << V.x << " " << V.y << " " << V.px << " " << V.py << " " << V.m << endl;
if( mat[V.x][V.y] == 'C' ){ res = V.m; return; }
traverse( V.x, V.y, V.px, V.py, V.m );
el _i;
for(int k=0;k<portalPos[V.x][V.y].size();k++){
_i = portalPos[V.x][V.y][k];
traverse( V.x, V.y, _i.x, _i.y, V.m );
}
}
}
int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
memset( visited, 0, sizeof visited );
cin >> N >> M;
for(int i=0;i<N;i++) for(int j=0;j<M;j++){
cin >> mat[i][j];
if( mat[i][j] == 'C' ){ endPos = el( i, j ); }
else if( mat[i][j] == 'S' ){ startPos = el( i, j ); }
}
for(int i=0;i<N;i++) for(int j=0;j<M;j++){
if( mat[i][j] == '#' ) continue;
if( isValid( i+1, j ) && mat[i+1][j] != '#' ){
int k;
for(k=i+1;k<N;k++) if( mat[k][j] == '#' ) break;
portalPos[i][j].push_back( el( k-1, j ) );
}
if( isValid( i-1, j ) && mat[i-1][j] != '#' ){
int k;
for(k=i-1;k>=0;k--) if( mat[k][j] == '#' ) break;
portalPos[i][j].push_back( el( k+1, j ) );
}
if( isValid( i, j+1 ) && mat[i][j+1] != '#' ){
int k;
for(k=j+1;k<M;k++) if( mat[i][k] == '#' ) break;
portalPos[i][j].push_back( el( i, k-1 ) );
}
if( isValid( i, j-1 ) && mat[i][j-1] != '#' ){
int k;
for(k=j-1;k>=0;k--) if( mat[i][k] == '#' ) break;
portalPos[i][j].push_back( el( i, k+1 ) );
}
// cout << "FOR POS " << i << " , " << j << endl;
// for(int k=0;k<portalPos[i][j].size();k++){
// cout << "\t" << portalPos[i][j][k].x << " " << portalPos[i][j][k].y << endl;
// }
}
res = -1;
bfs( el( startPos.x, startPos.y, N, M, 0 ) );
cout << res << endl;
}
Compilation message (stderr)
portals.cpp: In function 'void bfs(el)':
portals.cpp:69:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<portalPos[V.x][V.y].size();k++){
~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |