Submission #1176442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176442		hihihah	Robots (APIO13_robots)	C++20	30 / 100	10 ms	10312 KiB

robots

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define all(x) x.begin(), x.end()
#define pii pair<int, int>

int n, width, height;
char a[509][509];
pii pos[10];
int d[10][503][503];

int c[] = {-1, 1, 0, 0}; 
int h[] = {0, 0, -1, 1};
// up, down, left, right.

bool check_valid (int x, int y) {
    return (x > 0 && y > 0 && x <= width && y <= height && a[x][y] != 'x');
}

pii move (pii pos, int dir) {
    int x = pos.first + c[dir];
    int y = pos.second + h[dir];
    if (check_valid (x, y)) return make_pair (x, y);
    else return pos;
}

int turn (int dir, bool c) { // 0: clockwise, 1: counter_clockwise.
    if (c) {
        if (dir == 0) return 2;
        if (dir == 1) return 3;
        if (dir == 2) return 1;
        if (dir == 3) return 0;
    }
    else {
        if (dir == 0) return 3;
        if (dir == 1) return 2;
        if (dir == 2) return 0;
        if (dir == 3) return 1;
    }

    return 0;
}

void hihihah(){
    cin >> n >> height >> width;
    for (int i = 1; i <= width; i ++)
        for (int j = 1; j <= height; j ++)
            cin >> a[i][j];
    
    for (int i = 1; i <= width; i ++) {
        for (int j = 1; j <= height; j ++)
            if (a[i][j] >= '0' && a[i][j] <= '9') 
                pos[a[i][j] - '0'] = {i, j};
    }

    memset (d, -1, sizeof d);

    for (int i = 1; i <= n; i ++) {
        queue <pii> q;
        q.push (pos[i]);
        d[i][pos[i].first][pos[i].second] = 0;
        while (q.size()) {
            pii cur = q.front (); q.pop ();
            pii o = cur;
            int w = d[i][o.first][o.second];
            for (int j = 0; j < 4; j ++) {
                o = cur;
                int dir = j;
                while (1) {
                    if (a[o.first][o.second] == 'C') dir = turn (dir, 0);
                    if (a[o.first][o.second] == 'A') dir = turn (dir, 1);
                    pii nxt = move (o, dir);
                    if (nxt == o) break;
                    o = nxt;
                }
                if (d[i][o.first][o.second] == -1) {
                    d[i][o.first][o.second] = w + 1;
                    q.push (o);
                }
            }
        }

        // cout << i << '\n';
        // for (int j = 1; j <= width; j ++) {
        //     for (int k = 1; k <= height; k ++)
        //         if (d[i][j][k] == -1) cout << " " << d[i][j][k];
        //         else cout << "  " << d[i][j][k];
        //     cout << '\n';
        // }
        // cout << '\n';
    }

    if (n == 1) {
        cout << 0 << '\n';
        return;
    }

    int ans = 1e9;
    for (int i = 1; i <= width; i ++)
        for (int j = 1; j <= height; j ++) {
            if (d[1][i][j] != -1 && d[2][i][j] != -1) ans = min (ans, d[1][i][j] + d[2][i][j]);
        }

    if (ans == 1e9) cout << -1;
    else cout << ans;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    #define orz "mo"
    if(fopen(orz".inp", "r")){
        freopen(orz".inp", "r", stdin);
        freopen(orz".out", "w", stdout);
    }

    int t = 1;
    // cin >> t;
    while(t --){
        hihihah();
    }
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s";
    return 0;
}

Compilation message (stderr)

robots.cpp: In function 'int32_t main()':
robots.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen(orz".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         freopen(orz".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40