제출 #1271929

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271929		flaming_top1	Patkice II (COCI21_patkice2)	C++20	110 / 110	866 ms	79908 KiB

Main

#include <bits/stdc++.h>

#define SPED                                                                                                           \
    ios_base::sync_with_stdio(false);                                                                                  \
    cin.tie(0);                                                                                                        \
    cout.tie(0);

#define endl "\n"
#define fi first
#define se second
#define lint long long
#define fami signed
#define lore main
#define freefire freopen
#define Data tuple<lint, int, int>

const lint INF = 0x1f1f1f1f1f1f1f1f;
const lint NEG = 0xE1E1E1E1E1E1E1E1;

using namespace std;

int m, n;
pair<int, int> p, q, ways[4] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // >   <    v    ^
pair<int, int> trace[2005][2005];
string s[2005];
lint dist[2005][2005];

bool legit(int newx, int newy)
{
    return 1 <= newx and newx <= m and 1 <= newy and newy <= n;
}

int check(int z, char y)
{
    if (y == 'o')
        return 0;
    else if (y == '.')
        return 1;

    else if (z == 0 and y == '>')
        return 0;

    else if (z == 1 and y == '<')
        return 0;

    else if (z == 2 and y == 'v')
        return 0;

    else if (z == 3 and y == '^')
        return 0;

    return 1;
}

void dijkstra()
{
    memset(dist, 0x1f, sizeof dist);
    dist[p.fi][p.se] = 0;
    priority_queue<Data, vector<Data>, greater<Data>> pq;
    pq.emplace(0, p.fi, p.se);

    while (!pq.empty())
    {
        auto [du, x, y] = pq.top();
        pq.pop();

        if (du > dist[x][y])
            continue;

        for (int z = 0; z < 4; z++)
        {
            int newx = x + ways[z].fi;
            int newy = y + ways[z].se;
            if (!legit(newx, newy))
                continue;
            if (dist[newx][newy] > dist[x][y] + check(z, s[x][y]))
            {
                dist[newx][newy] = dist[x][y] + check(z, s[x][y]);
                trace[newx][newy] = {x, y};
                pq.emplace(dist[newx][newy], newx, newy);
            }
        }
    }
}

fami lore()
{
    SPED;
    cin >> m >> n;
    for (int i = 1; i <= m; i++)
    {
        cin >> s[i], s[i] = ' ' + s[i];
        for (int j = 1; j <= n; j++)
        {
            if (s[i][j] == 'o')
                p = {i, j};
            else if (s[i][j] == 'x')
                q = {i, j};
        }
    }
    dijkstra();
    cout << dist[q.fi][q.se] << endl;

    while (trace[q.fi][q.se] != p)
    {
        auto [x, y] = q;
        auto [tx, ty] = trace[q.fi][q.se];
        if (tx < x)
            s[tx][ty] = 'v';
        else if (tx > x)
            s[tx][ty] = '^';
        else if (ty < y)
            s[tx][ty] = '>';
        else if (ty > y)
            s[tx][ty] = '<';
        q = trace[q.fi][q.se];
    }

    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
            cout << s[i][j];
        cout << endl;
    }
}
// Let your soul wander where dreams are born.

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