oj.uz

Submission #135716

# Submission time Handle Problem Language Result Execution time Memory
135716 2019-07-24T09:58:49 Z Zex Portals (BOI14_portals) C++11
31 / 100
 140 ms 14124 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, 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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7032 KB Output is correct
2 Correct 7 ms 7032 KB Output is correct
3 Correct 9 ms 7032 KB Output is correct
4 Correct 9 ms 7032 KB Output is correct
5 Correct 10 ms 7032 KB Output is correct
6 Correct 9 ms 7032 KB Output is correct
7 Correct 9 ms 7032 KB Output is correct
8 Correct 10 ms 7032 KB Output is correct
9 Correct 9 ms 7032 KB Output is correct
10 Correct 9 ms 7032 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7032 KB Output is correct
2 Correct 9 ms 7032 KB Output is correct
3 Correct 9 ms 7032 KB Output is correct
4 Correct 9 ms 7032 KB Output is correct
5 Correct 9 ms 7032 KB Output is correct
6 Correct 9 ms 7032 KB Output is correct
7 Correct 8 ms 7032 KB Output is correct
8 Correct 9 ms 7032 KB Output is correct
9 Correct 40 ms 9208 KB Output is correct
10 Correct 51 ms 9112 KB Output is correct
11 Correct 140 ms 7304 KB Output is correct
12 Correct 61 ms 7520 KB Output is correct
13 Correct 46 ms 7672 KB Output is correct
14 Correct 7 ms 7032 KB Output is correct
15 Correct 25 ms 8440 KB Output is correct
16 Correct 8 ms 7160 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7032 KB Output is correct
2 Correct 8 ms 7032 KB Output is correct
3 Correct 8 ms 7032 KB Output is correct
4 Correct 8 ms 7032 KB Output is correct
5 Runtime error 18 ms 14124 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7160 KB Output is correct
2 Correct 8 ms 7032 KB Output is correct
3 Correct 8 ms 7032 KB Output is correct
4 Correct 8 ms 7032 KB Output is correct
5 Correct 8 ms 7032 KB Output is correct
6 Correct 7 ms 7032 KB Output is correct
7 Correct 8 ms 7036 KB Output is correct
8 Correct 8 ms 7032 KB Output is correct
9 Correct 44 ms 9336 KB Output is correct
10 Correct 49 ms 9080 KB Output is correct
11 Correct 131 ms 7244 KB Output is correct
12 Correct 56 ms 7416 KB Output is correct
13 Correct 47 ms 7800 KB Output is correct
14 Runtime error 17 ms 13944 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7032 KB Output is correct
2 Correct 7 ms 7032 KB Output is correct
3 Correct 8 ms 7032 KB Output is correct
4 Correct 8 ms 7032 KB Output is correct
5 Correct 8 ms 7096 KB Output is correct
6 Correct 8 ms 7032 KB Output is correct
7 Correct 8 ms 7160 KB Output is correct
8 Correct 8 ms 7032 KB Output is correct
9 Correct 40 ms 9316 KB Output is correct
10 Correct 50 ms 9180 KB Output is correct
11 Correct 130 ms 7224 KB Output is correct
12 Correct 56 ms 7416 KB Output is correct
13 Correct 45 ms 7672 KB Output is correct
14 Runtime error 18 ms 14044 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -