oj.uz

Submission #761309

# Submission time Handle Problem Language Result Execution time Memory
761309 2023-06-19T13:32:40 Z resolve100 Robots (APIO13_robots) C++14
10 / 100
 1 ms 340 KB 
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define read_file freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

using namespace std;

int n, w, h;
char grid[500][500];
ll dist_1[500][500];
ll dist_2[500][500];

bool visited_1[500][500];
bool visited_2[500][500];

vector<vector<vector<pair<int, int>>>> graph;

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

pair<int, int> traverse(int x, int y, int dir){
    while (true){
        if (grid[y][x] == 'A'){
            dir+=1; dir%=4;
        }
        else if (grid[y][x] == 'C'){
            dir+=3; dir%=4;
        }
        if (dir == 0){
            if (!valid(x-1, y)) return {x, y};
            else x--;
        }
        else if (dir == 1){
            if (!valid(x, y-1)) return {x, y};
            else y--;
        }
        else if (dir == 2){
            if (!valid(x+1, y)) return {x, y};
            else x++;
        }
        else if (dir == 3){
            if (!valid(x, y+1)) return {x, y};
            else y++;
        }
    }
}

void solve(){
    cin >> n >> w >> h;

    int x1, y1;
    int x2, y2;

    for (int i = 0; i < h; i++){
        vector<vector<pair<int, int>>> row;
        for (int j = 0; j < w; j++){
            vector<pair<int, int>> cell; row.push_back(cell);
            cin >> grid[i][j];
            dist_1[i][j] = 250000; visited_1[i][j] = false;
            dist_2[i][j] = 250000; visited_2[i][j] = false;
            if (grid[i][j] == '1') {
                dist_1[i][j] = 0; visited_1[i][j] = true;
                x1 = j; y1 = i;
            }
            else if (grid[i][j] == '2') {
                dist_2[i][j] = 0; visited_2[i][j] = true;
                x2 = j; y2 = i;
            }
        }
        graph.push_back(row);
    }


    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++){
            for (int k = 0; k < 4; k++){
                pair<int, int> par = traverse(j, i, k);
                int x = par.first; int y = par.second;
                if (x != j || y != i) {
                    graph.at(i).at(j).push_back(par);
                }
            }
        }
    }

    queue<pair<pair<int, int>, pair<int, int>>> q1;
    for (auto edge : graph.at(y1).at(x1)){
        q1.push({edge, {x1, y1}});
    }
    while (!q1.empty()){
        pair<pair<int, int>, pair<int, int>> curr = q1.front(); q1.pop();
        int x = curr.first.first; int y = curr.first.second;
        int pre_x = curr.second.first; int pre_y = curr.second.second;

        if (!visited_1[y][x]) {
            dist_1[y][x] = dist_1[pre_y][pre_x]+1;
            visited_1[y][x] = true;

            for (auto edge : graph.at(y).at(x)) q1.push({edge, {x, y}});
        }
    }

    for (auto edge : graph.at(y2).at(x2)){
        q1.push({edge, {x2, y2}});
    }
    while (!q1.empty()){
        pair<pair<int, int>, pair<int, int>> curr = q1.front(); q1.pop();
        int x = curr.first.first; int y = curr.first.second;
        int pre_x = curr.second.first; int pre_y = curr.second.second;

        if (!visited_2[y][x]) {
            dist_2[y][x] = dist_2[pre_y][pre_x]+1;
            visited_2[y][x] = true;

            for (auto edge : graph.at(y).at(x)) q1.push({edge, {x, y}});
        }
    }

    bool ok = false;
    ll ans = 250000;
    for (int y = 0; y < h; y++){
        for (int x = 0; x < w; x++){
            if (dist_1[y][x] != 250000 && dist_2[y][x] != 250000){
                ok = true;
                ans = min(ans, dist_1[y][x]+dist_2[y][x]);
            }
        }
    }


    if (ok) cout << ans << endl;
    else cout << -1 << endl;
}

int main(){
    fast;
    int t = 1;
    while (t--){
        solve();
    }
    return 0;
}

Compilation message

robots.cpp: In function 'void solve()':
robots.cpp:106:33: warning: 'y2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  106 |     for (auto edge : graph.at(y2).at(x2)){
      |                                 ^

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 40.0

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