제출 #1125676

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125676		underwaterkillerwhale	Patkice II (COCI21_patkice2)	C++20	110 / 110	342 ms	91256 KiB

Main

//#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define REB(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 2e3 + 7;
const int Mod = 1e9 + 7;///lon
const ll INF = 1e18 + 7;
const ll BASE = 137;
const int szBL = 450;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
char dir[4] = {'v', '^', '>', '<'};

struct Trace {
    int i, j;
    char dir;
};
int n, m;
char a[N][N];
int dp[N][N], vis[N][N];
Trace trace[N][N];

void solution () {
    cin >> n >> m;
    pii ST, ED;
    rep (i, 1, n) {
        string s; cin >> s;
        rep (j, 1, m) {
            a[i][j] = s[j - 1];
            if (a[i][j] == 'o') ST = {i, j};
            if (a[i][j] == 'x') ED = {i, j};
        }
    }
    deque<pii> dq;
    dq.push_back(ST);
    memset(dp, 0x3f, sizeof dp);
    dp[ST.fs][ST.se] = 0;
    while (!dq.empty()) {
        pii cur = dq.front();
        int i = cur.fs, j = cur.se;
        dq.pop_front();
        if (vis[i][j]) continue;
        vis[i][j] = 1;
        rep (k, 0, 3) {
            int ni = i + dx[k], nj = j + dy[k];
            int W = (dir[k] != a[i][j] && a[i][j] != 'o');
            if (ni < 1 || ni > n || nj < 1 || nj > m)
                continue;
            if (dp[ni][nj] > dp[i][j] + W) {
                dp[ni][nj] = dp[i][j] + W;
                trace[ni][nj] = {i, j, dir[k]};
                if (W == 0) dq.push_front(MP(ni, nj));
                else dq.push_back(MP(ni, nj));
            }
        }
    }
    cout << dp[ED.fs][ED.se] <<"\n";
    pii cur = ED;
    while (cur != ST) {
        Trace prv = trace[cur.fs][cur.se];
        if (MP(prv.i, prv.j) != ST)
        a[prv.i][prv.j] = prv.dir;
        cur = MP(prv.i, prv.j);
    }
    rep (i, 1, n) {
        rep (j, 1, m) {
            cout << a[i][j];
        }
        cout<<"\n";
    }
}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +32
rep (i, 0, n) {
    rep (j, 0, i) {
        if (j == 0 || j == i) {
            C[j][i] = 1;
            continue;
        }
        C[j][i] = (C[j][i - 1] + C[j - 1][i - 1]) % Mod;
    }
}
*/

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