oj.uz

Submission #407081

# Submission time Handle Problem Language Result Execution time Memory
407081 2021-05-18T12:51:30 Z Nodir_Bobiev Robots (APIO13_robots) C++17
30 / 100
 15 ms 6780 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 = 0; i < 4; 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 532 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Incorrect 15 ms 6780 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 532 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Incorrect 15 ms 6780 KB Output isn't correct
12 Halted 0 ms 0 KB -