답안 #1024043

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1024043	2024-07-15T10:46:09 Z	kustizus	Patkice II (COCI21_patkice2)	C++17	110 / 110	285 ms	56772 KB

Main

#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";
      |                 ^

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	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

Subtask #2

80.0 / 80.0

#	결과	실행 시간	메모리	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