oj.uz

Submission #407070

# Submission time Handle Problem Language Result Execution time Memory
407070 2021-05-18T12:33:41 Z Nodir_Bobiev Robots (APIO13_robots) C++17
10 / 100
 1 ms 332 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 directions[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( auto dir: directions ){
            int xx = x, yy = y;
            while( ok(xx+dir[0], yy+dir[1]) ){
                xx += dir[0];
                yy += dir[1];
            }
            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
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 Incorrect 1 ms 332 KB Output isn't correct
7 Halted 0 ms 0 KB -

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 Incorrect 1 ms 332 KB Output isn't correct
7 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 Incorrect 1 ms 332 KB Output isn't correct
7 Halted 0 ms 0 KB -