oj.uz

Submission #135800

# Submission time Handle Problem Language Result Execution time Memory
135800 2019-07-24T11:28:43 Z Zex Portals (BOI14_portals) C++11
70 / 100
 1000 ms 80400 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] ) );
        }

    }

}

priority_queue <el> q;

void wallBfs(){

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

        V = q.top();
        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 ) );
    }

    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 25 ms 24956 KB Output is correct
3 Correct 24 ms 24952 KB Output is correct
4 Correct 25 ms 24952 KB Output is correct
5 Correct 24 ms 24952 KB Output is correct
6 Correct 25 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 24 ms 24952 KB Output is correct
10 Correct 24 ms 24824 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 23 ms 24824 KB Output is correct
3 Correct 23 ms 24952 KB Output is correct
4 Correct 24 ms 24824 KB Output is correct
5 Correct 25 ms 24952 KB Output is correct
6 Correct 24 ms 24908 KB Output is correct
7 Correct 24 ms 24952 KB Output is correct
8 Correct 24 ms 24932 KB Output is correct
9 Correct 27 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 25308 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 24952 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 24 ms 24952 KB Output is correct
4 Correct 24 ms 24952 KB Output is correct
5 Correct 48 ms 27636 KB Output is correct
6 Correct 51 ms 27764 KB Output is correct
7 Correct 50 ms 28024 KB Output is correct
8 Correct 45 ms 27632 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24824 KB Output is correct
2 Correct 24 ms 24952 KB Output is correct
3 Correct 28 ms 24952 KB Output is correct
4 Correct 24 ms 24952 KB Output is correct
5 Correct 25 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 25 ms 24900 KB Output is correct
9 Correct 27 ms 25464 KB Output is correct
10 Correct 27 ms 25464 KB Output is correct
11 Correct 26 ms 25208 KB Output is correct
12 Correct 26 ms 25336 KB Output is correct
13 Correct 27 ms 25208 KB Output is correct
14 Correct 48 ms 27608 KB Output is correct
15 Correct 51 ms 27764 KB Output is correct
16 Correct 55 ms 28020 KB Output is correct
17 Correct 52 ms 28148 KB Output is correct
18 Correct 60 ms 28528 KB Output is correct
19 Correct 59 ms 28664 KB Output is correct
20 Correct 70 ms 30108 KB Output is correct
21 Correct 49 ms 27636 KB Output is correct
22 Correct 55 ms 27636 KB Output is correct
23 Correct 50 ms 27764 KB Output is correct
24 Correct 93 ms 29292 KB Output is correct
25 Correct 30 ms 24952 KB Output is correct
26 Correct 33 ms 25336 KB Output is correct
27 Correct 25 ms 24952 KB Output is correct
28 Correct 54 ms 27636 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24824 KB Output is correct
2 Correct 25 ms 24952 KB Output is correct
3 Correct 30 ms 24952 KB Output is correct
4 Correct 25 ms 24824 KB Output is correct
5 Correct 25 ms 24952 KB Output is correct
6 Correct 25 ms 24952 KB Output is correct
7 Correct 26 ms 24952 KB Output is correct
8 Correct 25 ms 24952 KB Output is correct
9 Correct 28 ms 25464 KB Output is correct
10 Correct 28 ms 25464 KB Output is correct
11 Correct 31 ms 25208 KB Output is correct
12 Correct 33 ms 25384 KB Output is correct
13 Correct 32 ms 25336 KB Output is correct
14 Correct 59 ms 27636 KB Output is correct
15 Correct 56 ms 27764 KB Output is correct
16 Correct 51 ms 28020 KB Output is correct
17 Correct 59 ms 28024 KB Output is correct
18 Correct 67 ms 28532 KB Output is correct
19 Correct 61 ms 28596 KB Output is correct
20 Correct 75 ms 30108 KB Output is correct
21 Correct 48 ms 27636 KB Output is correct
22 Correct 49 ms 27636 KB Output is correct
23 Correct 50 ms 27760 KB Output is correct
24 Correct 963 ms 80400 KB Output is correct
25 Execution timed out 1072 ms 55980 KB Time limit exceeded
26 Halted 0 ms 0 KB -