Submission #1024043

# Submission time Handle Problem Language Result Execution time Memory
1024043 2024-07-15T10:46:09 Z kustizus Patkice II (COCI21_patkice2) C++17
110 / 110
285 ms 56772 KB
#include <bits/stdc++.h>
using namespace std;
struct Node
{
    int x, y, d;
};
struct comp
{
    bool operator()(Node a, Node b)
    {
        return a.d > b.d;
    }
};
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    // freopen ("file.inp","r",stdin);
    // freopen ("file.out","w",stdout);
    int n, m;
    cin >> n >> m;
    vector<vector<char>> v(n, vector<char>(m));
    int Xo, Yo, Xx, Yx;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            cin >> v[i][j];
            if (v[i][j] == 'o')
                Xo = i, Yo = j;
            else if (v[i][j] == 'x')
                Xx = i, Yx = j;
        }
    vector<vector<int>> d(n, vector<int>(m, 1e9));
    vector<vector<pair<int, int>>> nxt(n, vector<pair<int, int>>(m));
    char H[5] = {'^', '>', '<', 'v', '.'};
    int Dx[5] = {-1, 0, 0, 1, 0}, Dy[5] = {0, 1, -1, 0, 0};
    priority_queue<Node, vector<Node>, comp> pq;
    pq.push({Xx, Yx, 0});
    d[Xx][Yx] = 0;
    while (!pq.empty())
    {
        Node p = pq.top();
        pq.pop();
        if (p.d != d[p.x][p.y])
            continue;
        bool ok = false;
        for (int k = 0; k < 4; k++)
        {
            int i1 = p.x + Dx[k], j1 = p.y + Dy[k];
            if (i1 < 0 || i1 >= n || j1 < 0 || j1 >= m)
                continue;
            if (v[i1][j1] == 'o')
            {
                d[i1][j1] = p.d;
                nxt[i1][j1] = {p.x, p.y};
                ok = true;
            }
            else
            {
                int o = p.d + (v[i1][j1] != H[3 - k]);
                if (d[i1][j1] > o)
                {
                    d[i1][j1] = o;
                    pq.push({i1, j1, o});
                    nxt[i1][j1] = {p.x, p.y};
                }
            }
        }
        if (ok)
            break;
    }
    cout << d[Xo][Yo] << "\n";
    int x = nxt[Xo][Yo].first, y = nxt[Xo][Yo].second;
    Xo = x, Yo = y;
    while (true)
    {
        if (Xo == Xx && Yo == Yx)
            break;
        int x = nxt[Xo][Yo].first, y = nxt[Xo][Yo].second;
        for (int k = 0; k < 4; k++)
            if (x - Dx[k] == Xo && y - Dy[k] == Yo)
            {
                v[Xo][Yo] = H[k];
                break;
            }
        Xo = x, Yo = y;
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            cout << v[i][j];
        cout << "\n";
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:78:28: warning: 'Yx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |         if (Xo == Xx && Yo == Yx)
      |                         ~~~^~~~~
Main.cpp:78:16: warning: 'Xx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |         if (Xo == Xx && Yo == Yx)
      |             ~~~^~~~~
Main.cpp:73:21: warning: 'Yo' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |     cout << d[Xo][Yo] << "\n";
      |                     ^
Main.cpp:73:17: warning: 'Xo' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |     cout << d[Xo][Yo] << "\n";
      |                 ^
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 38 ms 7628 KB Output is correct
7 Correct 41 ms 9416 KB Output is correct
8 Correct 90 ms 19280 KB Output is correct
9 Correct 107 ms 37804 KB Output is correct
10 Correct 283 ms 46416 KB Output is correct
11 Correct 285 ms 56772 KB Output is correct