Submission #761309

#	Time	Username	Problem	Language	Result	Execution time	Memory
761309		resolve100	Robots (APIO13_robots)	C++14	10 / 100	1 ms	340 KiB

robots

#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 (stderr)

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 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40