Submission #135763

#	Time	Username	Problem	Language	Result	Execution time	Memory
135763		Zex	Portals (BOI14_portals)	C++11	20 / 100	38 ms	26360 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, m;

    el(){}
    el( int _x, int _y ){ x = _x; y = _y; }
    el( int _x, int _y, int _m ){ x = _x; y = _y; m = _m; }

    bool operator < ( const el &o ) const{
        return m > o.m;
    }
};

const int maxN = 1001;
int N, M;
char mat[maxN][maxN];
bool visited[maxN][maxN];
el startPos, endPos;
vector <el> portalPos[maxN][maxN];
int res;
priority_queue <el> pq;

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 m ){
    int x, y; 

    x = Vx+1; y = Vy; if( !wall( x, y ) && !visited[x][y] ) pq.push( el( x, y, m+1 ) );
    x = Vx-1; y = Vy; if( !wall( x, y ) && !visited[x][y] ) pq.push( el( x, y, m+1 ) );
    x = Vx; y = Vy+1; if( !wall( x, y ) && !visited[x][y] ) pq.push( el( x, y, m+1 ) );
    x = Vx; y = Vy-1; if( !wall( x, y ) && !visited[x][y] ) pq.push( el( x, y, m+1 ) );

}

void bfs( el V ){

    while( !pq.empty() ) pq.pop();
    pq.push(V);

    while( !pq.empty() ){

        V = pq.top();
        pq.pop();

        if( visited[V.x][V.y] ) continue;
        visited[V.x][V.y] = 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.m );

        el _i;
        for(int k=0;k<portalPos[V.x][V.y].size();k++){
            _i = portalPos[V.x][V.y][k];
            pq.push( el( _i.x, _i.y, V.m+1 ) );
        }

    }

}

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( !wall( i+1, j ) && !wall( i-1, j ) && !wall( i, j+1 ) && !wall( i, j-1 ) ) 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, 0 ) );

    cout << res << endl;

}

Compilation message (stderr)

portals.cpp: In function 'void bfs(el)':
portals.cpp:66: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: 0 / 11
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30