Submission #657845

#	Time	Username	Problem	Language	Result	Execution time	Memory
657845		4EVER	Patkice (COCI20_patkice)	C++11	0 / 50	10 ms	16596 KiB

patkice

#include <bits/stdc++.h>
using namespace std;

#define PB push_back
#define ALL(i_) i_.begin(), i_.end()
#define LOG2(x) (31 - __builtin_clz(x))

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x > y + eps) {
            x = y;
            return true;
        } else return false;
    }

template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        X eps = 1e-9;
        if (x + eps < y) {
            x = y;
            return true;
        } else return false;
    }

template<class T>
    T Abs(const T &x) {
        return (x < 0 ? -x : x);
    }

const int mod = (int) 1e9 + 7;
const int oo = (int) 1e9 + 99;
const int maxn = (int) 2011;
const int LOG = (int) 20;
const char dir[] = { '>', '<', 'v', '^' };
const ii dxy[] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

int n, m;
char a[maxn][maxn], b[maxn][maxn];
int dp[maxn][maxn];
ii sta, fin;
ii pre[maxn][maxn];

struct data_{
    int u, v, w;
    bool operator < (const data_ &others) const{
        return (w > others.w);
    }
};

bool OK(int u, int v){
    return (u >= 1 && u <= n && v >= 1 && v <= m && (a[u][v] != 'o'));
}

void Trace(int i, int j){
    bool ok = 0;
    while(pre[i][j].first != -1){
        int p, q;
        for(int t = 0; t < 4; t++){
            p = i + dxy[t].first;
            q = j + dxy[t].second;
            if(p == sta.first && q == sta.second){
                ok = 1;
                break;
            }
            if(p == pre[i][j].first && q == pre[i][j].second){
                if(t == 0) t = 1;
                else if(t == 1) t = 0;
                else if(t == 2) t = 3;
                else if(t == 3) t = 2;
                b[p][q] = dir[t];
                break;
            }
        }
        if(ok) break;
        i = p, j = q;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(a[i][j] == 'o') cout << a[i][j];
            else cout << b[i][j];
        }
        cout << "\n";
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define TASK "PATKICE"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
    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') sta = {i, j};
            if(a[i][j] == 'x') fin = {i, j};
            pre[i][j] = {-1, -1};
            b[i][j] = a[i][j];
        }
    }
    memset(dp, 0x3f, sizeof dp);
    priority_queue<data_> que;
    dp[sta.first][sta.second] = 0;
    que.push({sta.first, sta.second, dp[sta.first][sta.second]});
    while(!que.empty()){
        int u = que.top().u;
        int v = que.top().v;
        int du = que.top().w;
        que.pop();
        if(dp[u][v] != du) continue;
        if(u == fin.first && v == fin.second){
            cout << dp[u][v] << "\n";
            Trace(u, v);
            return 0;
        }
        if(a[u][v] == 'o'){
            for(int i = 0; i < 4; i++){
                int p = u + dxy[i].first;
                int q = v + dxy[i].second;
                if(!OK(p, q)) continue;
                if(minimize(dp[p][q], dp[u][v])){
                    que.push({p, q, dp[p][q]});
                    pre[p][q] = {u, v};
                }
            }
        }
        else{
            for(int i = 0; i < 4; i++){
                int p, q;
                p = u + dxy[i].first;
                q = v + dxy[i].second;
                if(!OK(p, q)) continue;
                if(a[u][v] != dir[i]){
                    if(minimize(dp[p][q], dp[u][v] + 1)){
                        que.push({p, q, dp[p][q]});
                        pre[p][q] = {u, v};
                    }
                }
                else{
                    if(minimize(dp[p][q], dp[u][v])){
                        que.push({p,q , dp[p][q]});
                        pre[p][q] = {u, v};
                    }
                }
            }
        }
    }
    return 0;
}

Compilation message (stderr)

patkice.cpp: In function 'int main()':
patkice.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
patkice.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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