Submission #1125978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125978		whoknow	Patkice II (COCI21_patkice2)	C++20	110 / 110	301 ms	75384 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define MAXN 2005
#define ii pair<int,int>
#define bit(i,j) ((i>>j)&1)
#define sz(i) (int)i.size()
#define endl '\n'
using namespace std;
const int INF = 1e9 + 7;
int dx[] = {0, 0, -1, 1},
           dy[] = {1, -1, 0, 0};
int n, m;
char a[MAXN][MAXN], c[4] = {'>', '<', '^', 'v'};
ii st, ed;
namespace sub1
{
int dp[MAXN][MAXN];
struct trip
{
    int u, v, k;
};
trip trace[MAXN][MAXN];
bool check(int i, int j)
{
    return (i < 1 || j < 1 || i > n || j > m);
}
void bfs()
{
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            dp[i][j] = INF;
    deque<ii>q;
    q.push_front(st);
    dp[st.F][st.S] = 0;
    while(sz(q))
    {
        ii top = q.front();
        q.pop_front();
        int u = top.F, v = top.S;
        for(int i = 0; i < 4; i++)
        {
            int nx = u + dx[i], ny = v + dy[i];
            if(check(nx, ny))
                continue;
            int cost = (a[u][v] != 'o' && a[u][v] != c[i]);
            if(dp[nx][ny] > dp[u][v] + cost)
            {
                dp[nx][ny] = dp[u][v] + cost;
                trace[nx][ny] = {u, v, i};
                if(cost)
                    q.push_back({nx, ny});
                else
                    q.push_front({nx, ny});
            }
        }
    }
}
void query()
{
    queue<ii>q;
    q.push(ed);
    while(sz(q))
    {
        ii top = q.front();
        q.pop();
        if(a[top.F][top.S] == 'o')
            break;
        trip x = trace[top.F][top.S];
        q.push({x.u, x.v});
        if(a[x.u][x.v] != 'o')
            a[x.u][x.v] = c[x.k];
    }

}
void solve()
{
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            if(a[i][j] == 'o')
                st = {i, j};
            if(a[i][j] == 'x')
                ed = {i, j};
        }
    bfs();
    query();
    cout << dp[ed.F][ed.S] << endl;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
            cout << a[i][j];
        cout << endl;
    }
}
}
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> a[i][j];
    sub1::solve();
}

Compilation message (stderr)

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

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