oj.uz

답안 #381970

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
381970 2021-03-26T08:12:38 Z Vimmer Patkice II (COCI21_patkice2) C++14
110 / 110
 1125 ms 95212 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define N 100500
#define PB push_back
#define endl '\n'
#define pri(x) cout << x << endl
#define _ << " " <<
#define sz(x) int(x.size())
#define F first
#define S second
#define all(x) x.begin(), x.end()

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;

//typedef tree <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update> ord_set;

int f[2005][2005];

pair <int, int> from[2005][2005];

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

//    freopen("1.in", "r", stdin);

    for (int i = 0; i < 2005; i++)
        for (int j = 0; j < 2005; j++)
            f[i][j] = 1e9;

    int n, m;

    cin >> n >> m;

    string s[n];

    for (int i = 0; i < n; i++)
        cin >> s[i];

    set <pair <int, pair <int, int> > > se; se.clear();

    int xs, ys, xf, yf;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            if (s[i][j] == 'o')
            {
                xs = i; ys = j;
            }

            if (s[i][j] == 'x')
            {
                xf = i; yf = j;
            }
        }

    f[xs][ys] = 0;

    se.insert({0, {xs, ys}});

    while (sz(se))
    {
        pair <int, int> pt = (*se.begin()).S;

        se.erase(se.begin());

        int i = pt.F, j = pt.S;

        if (s[i][j] == 'x')
            break;

        int cx = pt.F, cy = pt.S;

        if (s[i][j] == '>')
            cy++;
                else if (s[i][j] == '<')
                    cy--;
                        else if (s[i][j] == '^')
                            cx--;
                                else if (s[i][j] == 'v')
                                    cx++;

        if (0 <= cx && cx < n && cy >= 0 && cy < m && f[cx][cy] > f[i][j])
        {
            f[cx][cy] = f[i][j];

            from[cx][cy] = {i, j};

            se.insert({f[cx][cy], {cx, cy}});
        }

        int b[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

        for (int i = 0; i < 4; i++)
        {
            int cx = pt.F + b[i][0];

            int cy = pt.S + b[i][1];

            if (0 <= cx && cx < n && cy >= 0 && cy < m && f[cx][cy] > f[pt.F][pt.S] + 1)
            {
                f[cx][cy] = f[pt.F][pt.S] + 1;

                from[cx][cy] = {pt.F, pt.S};

                se.insert({f[cx][cy], {cx, cy}});
            }
        }
    }

    pri(f[xf][yf] - 1);

    while (xf != xs || yf != ys)
    {
        pair <int, int> pt = from[xf][yf];

        char c;

        if (pt.S < yf)
            c = '>';
                else if (pt.S > yf)
                    c = '<';
                        else if (pt.F > xf)
                            c = '^';
                                else c = 'v';
        xf = pt.F;

        yf = pt.S;

        s[xf][yf] = c;
    }

    s[xs][ys] = 'o';

    for (int i = 0; i < n; i++)
        cout << s[i] << endl;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:139:13: warning: 'ys' may be used uninitialized in this function [-Wmaybe-uninitialized]
  139 |     s[xs][ys] = 'o';
      |             ^
Main.cpp:47:9: warning: 'xs' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |     int xs, ys, xf, yf;
      |         ^~
Main.cpp:117:17: warning: 'yf' may be used uninitialized in this function [-Wmaybe-uninitialized]
  117 |     pri(f[xf][yf] - 1);
      |                 ^
Main.cpp:117:17: warning: 'xf' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 16108 KB Output is correct
2 Correct 10 ms 16108 KB Output is correct
3 Correct 10 ms 16108 KB Output is correct
4 Correct 10 ms 16108 KB Output is correct
5 Correct 10 ms 16108 KB Output is correct

Subtask #2
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 16108 KB Output is correct
2 Correct 10 ms 16108 KB Output is correct
3 Correct 10 ms 16108 KB Output is correct
4 Correct 10 ms 16108 KB Output is correct
5 Correct 10 ms 16108 KB Output is correct
6 Correct 73 ms 21356 KB Output is correct
7 Correct 106 ms 31468 KB Output is correct
8 Correct 227 ms 30060 KB Output is correct
9 Correct 468 ms 60268 KB Output is correct
10 Correct 626 ms 49004 KB Output is correct
11 Correct 1125 ms 95212 KB Output is correct