oj.uz

Submission #381918

# Submission time Handle Problem Language Result Execution time Memory
381918 2021-03-26T06:57:48 Z VEGAnn Patkice II (COCI21_patkice2) C++14
110 / 110
 346 ms 47944 KB 
#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.0 / 30.0

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

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 52 ms 11244 KB Output is correct
7 Correct 56 ms 15596 KB Output is correct
8 Correct 132 ms 22252 KB Output is correct
9 Correct 208 ms 33044 KB Output is correct
10 Correct 322 ms 37612 KB Output is correct
11 Correct 346 ms 47944 KB Output is correct