제출 #135716

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
135716		Zex	포탈들 (BOI14_portals)	C++11	31 / 100	140 ms	14124 KiB

portals

#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;

}

컴파일 시 표준 에러 (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++){
                     ~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30