Submission #1135191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135191		DangKhoizzzz	Patkice II (COCI21_patkice2)	C++20	30 / 110	986 ms	531612 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

using namespace std;

const int INF = 1e9 + 7;
const int maxn = 2e3 + 7;

int n , m , sx , sy , ex , ey , d[maxn][maxn];
pii trace[maxn][maxn];
vector <arr3> g[maxn][maxn];
char a[maxn][maxn];
bool vis[maxn][maxn];

int dx[4] = {0 , 0 , 1 , -1};
int dy[4] = {1 , -1 , 0 , 0};

void bfs01()
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++) d[i][j] = INF;
    }

    deque <pii> Q;
    Q.push_back({sx , sy});
    d[sx][sy] = 0;

    while(!Q.empty())
    {
        int i = Q.front().fi;
        int j = Q.front().se;
        Q.pop_front();

        if(vis[i][j]) continue;
        vis[i][j] = 1;

        for(arr3 tmp: g[i][j])
        {
            int x = tmp[0];
            int y = tmp[1];
            int w = tmp[2];

            if(d[x][y] > d[i][j] + w)
            {
                d[x][y] = d[i][j] + w;
                trace[x][y] = {i , j};
                if(w == 0) Q.push_front({x , y});
                else Q.push_back({x , y});
            }
        }
    }
    cout << d[ex][ey] << '\n';
}

void trace_back()
{
    int i = ex , j = ey;

    while(true)
    {
        int x = trace[i][j].fi;
        int y = trace[i][j].se;

        if(x == i-1) a[x][y] = 'v';
        if(x == i+1) a[x][y] = '^';
        if(y == j-1) a[x][y] = '>';
        if(y == j+1) a[x][y] = '<';
        i = x , j = y;
        if(i == sx && j == sy) break;
    }
    a[sx][sy] = 'o';

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++) cout << a[i][j];
        cout << '\n';
    }
}

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            if(a[i][j] == 'o')
            {
                sx = i, sy = j;

                if(j > 1) g[i][j].push_back({i , j-1 , 0});
                if(j < m) g[i][j].push_back({i , j+1 , 0});
                if(i > 1) g[i][j].push_back({i-1 , j , 0});
                if(i < n) g[i][j].push_back({i+1 , j , 0});

            }
            else if(a[i][j] == 'x') ex = i , ey = j;
            else
            {
                if(a[i][j] == '<' && j > 1) g[i][j].push_back({i , j-1 , 0});
                if(a[i][j] == '>' && j < m) g[i][j].push_back({i , j+1 , 0});
                if(a[i][j] == '^' && i > 1) g[i][j].push_back({i-1 , j , 0});
                if(a[i][j] == 'v' && i < n) g[i][j].push_back({i+1 , j , 0});

                for(int k = 0; k < 4; k++)
                {
                    int x = i + dx[k];
                    int y = j + dy[k];

                    if(x == 0 || x == n+1 || y == 0 || y == m+1) continue;

                    g[i][j].push_back({x , y , 1});
                }
            }
        }
    }
    bfs01();
    trace_back();
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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