Submission #388229

#	Time	Username	Problem	Language	Result	Execution time	Memory
388229		phathnv	Patkice II (COCI21_patkice2)	C++11	110 / 110	245 ms	63880 KiB

Main

#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 / 30
• Subtask 2: 80 / 80