Submission #1125966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125966		whoknow	Patkice II (COCI21_patkice2)	C++20	30 / 110	2098 ms	145480 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];
bool visited[MAXN][MAXN][4];
short trace[MAXN][MAXN][4];
struct trip
{
    int u, v, k;
};
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);
}
bool minimize(int &a, int b)
{
    if(a > b)
        return a = b, 1;
    return 0;
}
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;
    priority_queue<trip,vector<trip>,cmp>q;
    for(int i = 0; i < 4; i++)
    {
        dp[st.F][st.S][i] = 0;
        q.push({st.F, st.S,i});
    }
    while(sz(q))
    {
        trip top = q.top();
        q.pop();
        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;
            if(minimize(dp[nx][ny][i], dp[u][v][k] + (a[u][v] != 'o' && a[u][v] != c[i])))
            {
                q.push({nx, ny,i});
                trace[nx][ny][i] = k;
            }
        }
    }
}
void query(int k)
{
    queue<trip>q;
    q.push({ed.F, ed.S, k});
    while(sz(q))
    {
        trip top = q.front();
        q.pop();
        int u = top.u, v = top.v, k = top.k;
        if(a[u][v] == 'o')
            break;
        int nx = u + -1 * dx[k], ny = v + -1 * dy[k];
        q.push({nx, ny, trace[u][v][k]});
        if(a[nx][ny] != 'o')
            a[nx][ny] = c[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:117:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  117 | main()
      | ^~~~

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