Submission #1125969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125969		whoknow	Patkice II (COCI21_patkice2)	C++20	110 / 110	894 ms	273356 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][4];
struct trip
{
    int u, v, k;
};
trip trace[MAXN][MAXN][4];
struct cmp
{
    bool operator()(trip x, trip y)
    {
        return dp[x.u][x.v][x.k] > dp[y.u][y.v][y.k];
    }
};
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++)
            for(int k = 0; k < 4; k++)
                dp[i][j][k] = INF;
    deque<trip>q;
    for(int i = 0; i < 4; i++)
    {
        dp[st.F][st.S][i] = 0;
        q.push_front({st.F, st.S, i});
    }
    while(sz(q))
    {
        trip top = q.front();
        q.pop_front();
        int u = top.u, v = top.v, k = top.k;
        if(u == ed.F && v == ed.S)
            return ;
        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][i] > dp[u][v][k] + cost)
            {
                dp[nx][ny][i] = dp[u][v][k] + cost;
                trace[nx][ny][i] = {u, v, k};
                if(cost)
                    q.push_back({nx, ny, i});
                else
                    q.push_front({nx, ny, i});
            }
        }
    }
}
void query(int k)
{
    queue<trip>q;
    q.push({ed.F, ed.S, k});
    while(sz(q))
    {
        trip top = q.front();
        q.pop();
        if(a[top.u][top.v] == 'o')
            break;
        trip x = trace[top.u][top.v][top.k];
        q.push(x);
        if(a[x.u][x.v] != 'o')
            a[x.u][x.v] = c[top.k];
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
            cout << a[i][j];
        cout << endl;
    }
}
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();
    int res = 0;
    for(int i = 0; i < 4; i++)
        if(dp[ed.F][ed.S][res] > dp[ed.F][ed.S][i])
            res = i;
    cout << dp[ed.F][ed.S][res] << endl;
    query(res);
}
}
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:114:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  114 | main()
      | ^~~~

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