oj.uz

Submission #407079

# Submission time Handle Problem Language Result Execution time Memory
407079 2021-05-18T12:50:24 Z Nodir_Bobiev Robots (APIO13_robots) C++17
0 / 100
 1500 ms 204 KB 
/* In the name of Allah */
# include <bits/stdc++.h>
using namespace std;

const int inf = 1000000;
int n, w, h, dist[10][600][600];
int dirs[4][2] = { {0, -1}, {-1, 0}, {0, 1}, {1, 0} };
string grid[600];

bool ok( int x, int y ){
    return( 0 <= x && x < h && 0 <= y && y < w && grid[x][y] != 'x');
}

void bfs( int x, int y, int id ){
    for( int i = 0; i < h; i ++ )
        for( int j = 0; j < w; j ++ )
            dist[id][i][j] = inf;
    dist[id][x][y] = 0;
    queue < pair < int, int > > q;
    q.push({x,y});
    while( !q.empty() ){
        auto fr = q.front(); q.pop();
        x = fr.first; y = fr.second;
        for( int i = 1; i < 5; i ++ ){
            int xx = x, yy = y, j = i;
            while( ok(xx+dirs[j][0], yy+dirs[j][1]) ){
                xx += dirs[j][0];
                yy += dirs[j][1];
                if( grid[xx][yy] == 'A' ){
                    j --;
                    if( j < 0 ) j += 4;
                }
                else if( grid[xx][yy] == 'C' ){
                    j ++;
                    if( j > 3 ) j -= 4;
                }
            }
            if( dist[id][xx][yy] == inf ){
                dist[id][xx][yy] = dist[id][x][y] + 1;
                q.push({xx,yy});
            }
        }
    }
}

int main(){
    cin >> n >> w >> h;
    for( int i = 0; i < h; i ++ ){
        cin >> grid[i];
    }
    for( int i = 0; i < h; i ++ ){
        for( int j = 0; j < w; j ++ ){
            if( '1' <= grid[i][j] && grid[i][j] <= '9' )
                bfs(i, j, grid[i][j] - '0');
        }
    }
    int ans = inf;
    for( int i = 0; i < h; i ++ ){
        for( int j = 0; j < w; j ++ ){
            ans = min( ans, dist[1][i][j] + dist[2][i][j] );
        }
    }
    if( ans == inf ) cout << -1;
    else cout << ans;
}
/*
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1567 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1567 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1567 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1567 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -