oj.uz

Submission #135751

# Submission time Handle Problem Language Result Execution time Memory
135751 2019-07-24T10:31:44 Z Zex Portals (BOI14_portals) C++11
20 / 100
 35 ms 26332 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; }
};

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

    x = Vx+1; y = Vy; if( !wall( x, y ) && !visited[x][y] ) q.push( el( x, y, m+1 ) );
    x = Vx-1; y = Vy; if( !wall( x, y ) && !visited[x][y] ) q.push( el( x, y, m+1 ) );
    x = Vx; y = Vy+1; if( !wall( x, y ) && !visited[x][y] ) q.push( el( x, y, m+1 ) );
    x = Vx; y = Vy-1; if( !wall( x, y ) && !visited[x][y] ) q.push( el( x, y, 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] ) 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];
            q.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

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

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24824 KB Output is correct
2 Correct 24 ms 24824 KB Output is correct
3 Correct 24 ms 24824 KB Output is correct
4 Correct 25 ms 24864 KB Output is correct
5 Correct 24 ms 24824 KB Output is correct
6 Correct 25 ms 24824 KB Output is correct
7 Correct 29 ms 24824 KB Output is correct
8 Correct 24 ms 24824 KB Output is correct
9 Correct 24 ms 24824 KB Output is correct
10 Incorrect 24 ms 24824 KB Output isn't correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24892 KB Output is correct
2 Correct 24 ms 24824 KB Output is correct
3 Correct 25 ms 24796 KB Output is correct
4 Correct 25 ms 24952 KB Output is correct
5 Correct 24 ms 24824 KB Output is correct
6 Correct 25 ms 24824 KB Output is correct
7 Correct 25 ms 24952 KB Output is correct
8 Correct 24 ms 24824 KB Output is correct
9 Correct 25 ms 24952 KB Output is correct
10 Incorrect 25 ms 24952 KB Output isn't correct
11 Halted 0 ms 0 KB -

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 24824 KB Output is correct
3 Correct 24 ms 24824 KB Output is correct
4 Correct 24 ms 24824 KB Output is correct
5 Correct 33 ms 25920 KB Output is correct
6 Correct 34 ms 26076 KB Output is correct
7 Correct 35 ms 26332 KB Output is correct
8 Correct 31 ms 25980 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24824 KB Output is correct
2 Correct 25 ms 24824 KB Output is correct
3 Correct 27 ms 24900 KB Output is correct
4 Correct 25 ms 24884 KB Output is correct
5 Correct 25 ms 24824 KB Output is correct
6 Correct 24 ms 24824 KB Output is correct
7 Correct 24 ms 24824 KB Output is correct
8 Correct 25 ms 24952 KB Output is correct
9 Correct 25 ms 24952 KB Output is correct
10 Incorrect 25 ms 24952 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24824 KB Output is correct
2 Correct 24 ms 24824 KB Output is correct
3 Correct 30 ms 24824 KB Output is correct
4 Correct 25 ms 24824 KB Output is correct
5 Correct 25 ms 24824 KB Output is correct
6 Correct 25 ms 24824 KB Output is correct
7 Correct 30 ms 24824 KB Output is correct
8 Correct 24 ms 24824 KB Output is correct
9 Correct 25 ms 25052 KB Output is correct
10 Incorrect 25 ms 24952 KB Output isn't correct
11 Halted 0 ms 0 KB -