oj.uz

답안 #381971

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
381971 2021-03-26T08:15:09 Z NONAME Patkice II (COCI21_patkice2) C++17
30 / 110
 4 ms 1388 KB 
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, const T b) {a = min(a, b); return (a == b);}
template <typename T> inline bool chmax(T& a, const T b) {a = max(a, b); return (a == b);}

const int steps[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int n, m, sx, sy, ex, ey;
int a[100][100], d[100][100];
array <int, 3> pr[100][100];

inline void cls() {}

void solve() {
    cls();

    string st = ".v>^<ox";

    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            d[i][j] = 1e9;
            pr[i][j] = {-1, -1, -1};
            char c;
            cin >> c;
            if (c == '.') {
                a[i][j] = 0;
            }
            if (c == 'v') {
                a[i][j] = 1;
            }
            if (c == '>') {
                a[i][j] = 2;
            }
            if (c == '^') {
                a[i][j] = 3;
            }
            if (c == '<') {
                a[i][j] = 4;
            }
            if (c == 'o') {
                a[i][j] = 5;
                sx = i, sy = j;
            }
            if (c == 'x') {
                a[i][j] = 6;
                ex = i, ey = j;
            }
        }
    }

    queue <array <int, 2> > q;
    q.push({sx, sy});
    d[sx][sy] = 0;
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        int x = cur[0], y = cur[1];
        if (a[x][y] == 6) {
            continue;
        }

        if ((x == sx) && (y == sy)) {
            for (int i = 0; i < 4; ++i) {
                int cx = x + steps[i][0];
                int cy = y + steps[i][1];
                if ((cx >= 0) && (cx < n) && (cy >= 0) && (cy < m)) {
                    d[cx][cy] = 0;
                    pr[cx][cy] = {x, y, i + 1};
                    q.push({cx, cy});
                }
            }
        } else {
            for (int i = 0; i < 4; ++i) {
                int cx = x + steps[i][0];
                int cy = y + steps[i][1];

                if ((cx >= 0) && (cx < n) && (cy >= 0) && (cy < m) && ((d[x][y] + ((i + 1) != a[x][y])) < d[cx][cy])) {
                    d[cx][cy] = d[x][y] + ((i + 1) != a[x][y]);
                    pr[cx][cy] = {x, y, i + 1};
                    q.push({cx, cy});
                }
            }
        }
    }

    int x = ex, y = ey, tp = -1;
    while ((x != sx) || (y != sy)) {
        if (tp != -1) {
            a[x][y] = tp;
        }
        int ox = x, oy = y;
        x = pr[ox][oy][0];
        y = pr[ox][oy][1];
        tp = pr[ox][oy][2];
    }

    cout << d[ex][ey] << "\n";
    for (int i = 0; i < n; ++i, cout << "\n") {
        for (int j = 0; j < m; ++j) {
            cout << st[a[i][j]];
        }
    }
}

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

    int t = 1;
    #ifdef _LOCAL
        system("color a");
        freopen("in.txt", "r", stdin);
        cin >> t;
    #endif

    for (int i = 1; i <= t; ++i) {
        cerr << "Case #" << i << ": \n";
        solve();
        cerr << "\n";
    }

    return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
0.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Runtime error 4 ms 1388 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -