oj.uz

Submission #706609

# Submission time Handle Problem Language Result Execution time Memory
706609 2023-03-07T06:35:46 Z YugiHacker Patkice II (COCI21_patkice2) C++14
110 / 110
 270 ms 47112 KB 
/*
	www.youtube.com/YugiHackerChannel
	oj.vnoi.info/user/YugiHackerKhongCopCode
*/
#include<bits/stdc++.h>
#define el cout<<"\n"
#define f0(i,n) for(int i=0;i<n;++i)
#define f1(i,n) for(int i=1;i<=n;++i)
#define maxn 2003
using namespace std;
int n, m, s[2], t[2];
char a[maxn][maxn];
int d[maxn][maxn], tr[maxn][maxn];
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
char dir[] = {'<', '>', '^', 'v'};
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    f1 (i, n) f1 (j, m)
    {
        cin >> a[i][j];
        if (a[i][j] == 'o') s[0] = i, s[1] = j;
        if (a[i][j] == 'x') t[0] = i, t[1] = j;
        d[i][j] = 1e4;
    }
    d[s[0]][s[1]] = 0;
    deque <pair<int, int>> q;
    q.push_front({s[0], s[1]});
    while (q.size())
    {
        pair <int, int> p = q.front();
        q.pop_front();
        int u = p.first;
        int v = p.second;
        f0 (i, 4)
        {
            int uu = u + dx[i], vv = v + dy[i];
            int cost = (dir[i] != a[u][v]);
            if (a[u][v] == 'o') cost = 0;
            if (uu > 0 && vv > 0 && uu <= n && vv <= m && a[uu][vv] != 'o')
            {
                if (d[u][v] + cost < d[uu][vv])
                {
                    d[uu][vv] = d[u][v] + cost;
                    tr[uu][vv] = i;
                    if (cost == 0) q.push_front({uu, vv});
                    else q.push_back({uu, vv});
                }
            }
        }
    }
    int u = t[0], v = t[1];
    cout << d[u][v]; el;
    while (u != s[0] || v != s[1])
    {
        int x = tr[u][v];
        u -= dx[x];
        v -= dy[x];
        if (a[u][v] == 'o') break;
        a[u][v] = dir[x];
    }
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++) cout << a[i][j];
        el;
    }
}

Compilation message

Main.cpp:17:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   17 | main()
      | ^~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 0 ms 340 KB Output is correct

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 39 ms 11160 KB Output is correct
7 Correct 40 ms 15492 KB Output is correct
8 Correct 101 ms 22048 KB Output is correct
9 Correct 164 ms 32096 KB Output is correct
10 Correct 233 ms 37320 KB Output is correct
11 Correct 270 ms 47112 KB Output is correct