Submission #135716

#TimeUsernameProblemLanguageResultExecution timeMemory
135716ZexPortals (BOI14_portals)C++11
31 / 100
140 ms14124 KiB
#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 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...