oj.uz

Submission #135798

# Submission time Handle Problem Language Result Execution time Memory
135798 2019-07-24T11:24:51 Z Zex Portals (BOI14_portals) C++11
70 / 100
 1000 ms 79108 KB 
#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 nearestWall[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 + nearestWall[V.x][V.y] ) );
        }

    }

}

queue <el> q;

void wallBfs(){

    el V;
    while( !q.empty() ){

        V = q.front();
        q.pop();

        if( nearestWall[V.x][V.y] <= V.m ) continue;
        nearestWall[V.x][V.y] = V.m;

        int x, y;

        x = V.x+1; y = V.y; if( !wall( x, y ) && nearestWall[x][y] > V.m+1 ) q.push( el( x, y, V.m+1 ) );
        x = V.x-1; y = V.y; if( !wall( x, y ) && nearestWall[x][y] > V.m+1 ) q.push( el( x, y, V.m+1 ) );
        x = V.x; y = V.y+1; if( !wall( x, y ) && nearestWall[x][y] > V.m+1 ) q.push( el( x, y, V.m+1 ) );
        x = V.x; y = V.y-1; if( !wall( x, y ) && nearestWall[x][y] > V.m+1 ) q.push( el( x, y, V.m+1 ) );


    }

}

void findNearestWalls(){

    for(int k=0;k<N;k++){
        if( mat[k][0] != '#' )   q.push( el( k, 0, 1 ) );
        if( mat[k][M-1] != '#' ) q.push( el( k, M-1, 1 ) );
    }
    for(int k=0;k<M;k++){
        if( mat[0][k] != '#' )   q.push( el( 0, k, 1 ) );
        if( mat[N-1][k] != '#' ) q.push( el( N-1, k, 1 ) );
    }

    wallBfs();

    for(int i=0;i<N;i++) for(int j=0;j<M;j++){
        if( mat[i][j] != '#' ) continue;
        q.push( el( i, j, 0 ) );
    }

    wallBfs();

}

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++){

        nearestWall[i][j] = INF;

        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;
        // }

    }

    findNearestWalls();

    res = -1;
    bfs( el( startPos.x, startPos.y, 0 ) );

    cout << res << endl;

}

Compilation message

portals.cpp: In function 'void bfs(el)':
portals.cpp:67: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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24824 KB Output is correct
2 Correct 24 ms 24924 KB Output is correct
3 Correct 24 ms 24952 KB Output is correct
4 Correct 24 ms 24824 KB Output is correct
5 Correct 24 ms 24896 KB Output is correct
6 Correct 25 ms 24952 KB Output is correct
7 Correct 31 ms 24912 KB Output is correct
8 Correct 29 ms 24952 KB Output is correct
9 Correct 24 ms 24952 KB Output is correct
10 Correct 24 ms 24952 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24824 KB Output is correct
2 Correct 24 ms 24892 KB Output is correct
3 Correct 24 ms 24952 KB Output is correct
4 Correct 24 ms 24824 KB Output is correct
5 Correct 24 ms 24952 KB Output is correct
6 Correct 25 ms 24952 KB Output is correct
7 Correct 29 ms 24828 KB Output is correct
8 Correct 25 ms 24924 KB Output is correct
9 Correct 27 ms 25464 KB Output is correct
10 Correct 28 ms 25464 KB Output is correct
11 Correct 25 ms 25208 KB Output is correct
12 Correct 25 ms 25208 KB Output is correct
13 Correct 25 ms 25336 KB Output is correct
14 Correct 24 ms 24824 KB Output is correct
15 Correct 26 ms 25336 KB Output is correct
16 Correct 24 ms 24824 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24824 KB Output is correct
2 Correct 24 ms 24952 KB Output is correct
3 Correct 23 ms 24828 KB Output is correct
4 Correct 24 ms 24952 KB Output is correct
5 Correct 41 ms 27256 KB Output is correct
6 Correct 42 ms 27356 KB Output is correct
7 Correct 42 ms 27512 KB Output is correct
8 Correct 35 ms 27356 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24824 KB Output is correct
2 Correct 23 ms 24952 KB Output is correct
3 Correct 28 ms 24952 KB Output is correct
4 Correct 24 ms 24824 KB Output is correct
5 Correct 29 ms 24952 KB Output is correct
6 Correct 28 ms 24952 KB Output is correct
7 Correct 25 ms 24896 KB Output is correct
8 Correct 24 ms 24952 KB Output is correct
9 Correct 26 ms 25464 KB Output is correct
10 Correct 26 ms 25464 KB Output is correct
11 Correct 25 ms 25208 KB Output is correct
12 Correct 26 ms 25208 KB Output is correct
13 Correct 26 ms 25208 KB Output is correct
14 Correct 40 ms 27256 KB Output is correct
15 Correct 42 ms 27384 KB Output is correct
16 Correct 42 ms 27512 KB Output is correct
17 Correct 44 ms 27512 KB Output is correct
18 Correct 52 ms 28024 KB Output is correct
19 Correct 53 ms 28716 KB Output is correct
20 Correct 64 ms 30068 KB Output is correct
21 Correct 39 ms 27256 KB Output is correct
22 Correct 39 ms 27256 KB Output is correct
23 Correct 41 ms 27512 KB Output is correct
24 Correct 85 ms 29304 KB Output is correct
25 Correct 24 ms 24924 KB Output is correct
26 Correct 25 ms 25208 KB Output is correct
27 Correct 24 ms 24824 KB Output is correct
28 Correct 39 ms 27452 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24796 KB Output is correct
2 Correct 29 ms 24952 KB Output is correct
3 Correct 30 ms 24952 KB Output is correct
4 Correct 24 ms 24824 KB Output is correct
5 Correct 24 ms 24952 KB Output is correct
6 Correct 24 ms 24952 KB Output is correct
7 Correct 24 ms 24952 KB Output is correct
8 Correct 24 ms 24952 KB Output is correct
9 Correct 26 ms 25436 KB Output is correct
10 Correct 26 ms 25464 KB Output is correct
11 Correct 25 ms 25336 KB Output is correct
12 Correct 25 ms 25208 KB Output is correct
13 Correct 26 ms 25208 KB Output is correct
14 Correct 40 ms 27256 KB Output is correct
15 Correct 44 ms 27384 KB Output is correct
16 Correct 42 ms 27640 KB Output is correct
17 Correct 45 ms 27512 KB Output is correct
18 Correct 56 ms 28224 KB Output is correct
19 Correct 53 ms 28536 KB Output is correct
20 Correct 64 ms 30120 KB Output is correct
21 Correct 41 ms 27256 KB Output is correct
22 Correct 47 ms 27384 KB Output is correct
23 Correct 49 ms 27384 KB Output is correct
24 Correct 713 ms 79108 KB Output is correct
25 Execution timed out 1084 ms 57592 KB Time limit exceeded
26 Halted 0 ms 0 KB -