Submission #381918

#	Time	Username	Problem	Language	Result	Execution time	Memory
381918		VEGAnn	Patkice II (COCI21_patkice2)	C++14	110 / 110	346 ms	47944 KiB

Main

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define PB push_back
#define i2 array<int,2>
using namespace std;
typedef long long ll;
const int MX = int(1e7) + 10;
const int oo = 2e9;
const int N = 2010;
int n, m, sx, sy, ex, ey;
int dst[N][N], pre[N][N], go[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1 ,0}};
string sgo = "><v^";
char c[N][N];
deque<i2> dq;

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

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> m;

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++){
        cin >> c[i][j];

        dst[i][j] = oo;

        if (c[i][j] == 'o'){
            sx = i;
            sy = j;
        }

        if (c[i][j] == 'x'){
            ex = i;
            ey = j;
        }
    }

    dst[sx][sy] = 0;
    dq.push_front({sx, sy});

    while (sz(dq) > 0){
        i2 CR = dq.front(); dq.pop_front();

        int x = CR[0], y = CR[1];

        for (int it = 0; it < 4; it++){
            int cx = x + go[it][0];
            int cy = y + go[it][1];

            if (cx < 0 || cy < 0 || cx >= n || cy >= m) continue;

            int nw = dst[x][y] + bool(sgo[it] != c[x][y]);

            if (nw < dst[cx][cy]){
                dst[cx][cy] = nw;
                pre[cx][cy] = it;

                if (sgo[it] == c[x][y])
                    dq.push_front({cx, cy});
                else dq.push_back({cx, cy});
            }
        }
    }

    cout << dst[ex][ey] - 1 << '\n';

    int x = ex, y = ey;

    while (1){
        int tp = pre[x][y];

        x -= go[tp][0];
        y -= go[tp][1];

        c[x][y] = sgo[tp];

        if (x == sx && y == sy) break;
    }

    c[sx][sy] = 'o';

    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++)
            cout << c[i][j];
        cout << '\n';
    }

    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 80 / 80