oj.uz

Submission #388229

# Submission time Handle Problem Language Result Execution time Memory
388229 2021-04-10T15:19:47 Z phathnv Patkice II (COCI21_patkice2) C++11
110 / 110
 245 ms 63880 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 2007;

const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const char ch[4] = {'^', '>', 'v', '<'};

int r, c, b[N][N], sX, sY, tX, tY, dist[N][N], trace[N][N];
char a[N][N];

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

    cin >> r >> c;
    for(int i = 1; i <= r; i++)
        cin >> (a[i] + 1);

    memset(b, -1, sizeof(b));
    for(int i = 1; i <= r; i++)
        for(int j = 1; j <= c; j++){
            for(int x = 0; x < 4; x++)
                if (a[i][j] == ch[x])
                    b[i][j] = x;
            if (a[i][j] == 'o'){
                sX = i;
                sY = j;
            }
            if (a[i][j] == 'x'){
                tX = i;
                tY = j;
            }
        }

    memset(trace, -1, sizeof(trace));
    memset(dist, 0x3f, sizeof(trace));
    deque<pair<int, int>> dq;
    dist[sX][sY] = 0;
    trace[sX][sY] = -2;
    dq.push_front({sX, sY});
    while (!dq.empty()){
        int x = dq.front().first;
        int y = dq.front().second;
        dq.pop_front();

        for(int dir = 0; dir < 4; dir++){
            int nX = x + dx[dir];
            int nY = y + dy[dir];
            if (nX < 1 || r < nX || nY < 1 || c < nY)
                continue;
            int nDist = dist[x][y] + (b[x][y] != dir);
            if (dist[nX][nY] > nDist){
                dist[nX][nY] = nDist;
                trace[nX][nY] = dir;
                if (b[x][y] != dir)
                    dq.push_back({nX, nY});
                else
                    dq.push_front({nX, nY});
            }
        }
    }

    int ans = dist[tX][tY] - 1;
    while (tX != sX || tY != sY){
        int dir = trace[tX][tY];
        tX -= dx[dir];
        tY -= dy[dir];
        if (dist[tX][tY])
            a[tX][tY] = ch[dir];
    }

    cout << ans << '\n';
    for(int i = 1; i <= r; i++)
        cout << (a[i] + 1) << '\n';
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47556 KB Output is correct
2 Correct 20 ms 47564 KB Output is correct
3 Correct 21 ms 47596 KB Output is correct
4 Correct 22 ms 47660 KB Output is correct
5 Correct 22 ms 47616 KB Output is correct

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 47556 KB Output is correct
2 Correct 20 ms 47564 KB Output is correct
3 Correct 21 ms 47596 KB Output is correct
4 Correct 22 ms 47660 KB Output is correct
5 Correct 22 ms 47616 KB Output is correct
6 Correct 53 ms 49324 KB Output is correct
7 Correct 55 ms 50748 KB Output is correct
8 Correct 101 ms 50956 KB Output is correct
9 Correct 149 ms 56576 KB Output is correct
10 Correct 233 ms 57192 KB Output is correct
11 Correct 245 ms 63880 KB Output is correct