Submission #384112

#TimeUsernameProblemLanguageResultExecution timeMemory
384112nguyen31hoang08minh2003Patkice (COCI20_patkice)C++14
0 / 50
3 ms492 KiB
#include <bits/stdc++.h>
#define fore(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define fort(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define ford(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define id(x, y) ((x) * c + (y))
#define row(p) ((p) / c)
#define column(p) ((p) % c)
using namespace std;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

const int maxR = 105, maxC = 105,
          inf = 0x3f3f3f3f,
          t[4][2] = {{0, 1}, {-1, 0}, {1, 0}, {0, -1} };
const char currents[4] = {'>', '^', 'v', '<'},
           directions[4] = {'E', 'N', 'S', 'W'};//alphabetical order

int r, c, d[maxR][maxC];
char ocean[maxR][maxC];
//ii calm[maxR][maxC];
ii ducks;
//queue<ii> q;
deque<ii> dq;

//ii Calm(const int x, const int y) /*moving backward*/ {
//    if (!calm[x][y].fi)/*not visited yet*/ {
//        fore(i, 0, 4)
//            if (ocean[x][y] == currents[i]) {
//                return calm[x][y] = Calm(x - t[i][0], y - t[i][1]);
//            }
//        calm[x][y] = ii(x, y);
//    };
//    return calm[x][y];
//}

int main() {
    #ifndef ONLINE_JUDGE
        freopen("main.INP", "r", stdin);
    #endif // ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    memset(d, inf, sizeof(d));
    cin >> r >> c;
    fore(i, 0, r) {
        cin >> ocean[i];
        fore(j, 0, c)
            if (ocean[i][j] == 'x') {
                d[i][j] = 0;
//                q.push(ii(i, j));
                dq.pb(ii(i, j));
            } else if (ocean[i][j] == 'o')
                ducks = ii(i, j);
    }
//    while (!q.empty()) {
//        const int u = q.front().fi, v = q.front().se;
//        q.pop();
//        fore(k, 0, 4) {
//            const int x = u - t[k][0], y = v - t[k][1];
//            const ii nxt = Calm(x, y);
//            if (mini(d[nxt.fi][nxt.se], d[u][v] + 1))
//                q.push(nxt);
//        }
//    }
    while (!dq.empty()) {
        const int u = dq.front().fi, v = dq.front().se;
        dq.pop_front();
        int x = -1, y = -1;
        fore(i, 0, 4) {
            x = u - t[i][0];
            y = v - t[i][1];
            if (x < 0 || y < 0 || x >= r || y >= c)
                continue;
            if (currents[i] == ocean[u][v]) {
                if (mini(d[x][y], d[u][v]))
                    dq.push_front(ii(x, y));
            } else {
                if (mini(d[x][y], d[u][v] + 1))
                    dq.push_back(ii(x, y));
            }
        }
    }
    fore(x, 0, r) {
        fore(y, 0, c)
            if (d[x][y] == inf)
                cerr << setw(3) << "oo ";
            else
                cerr << setw(3) << d[x][y] << ' ';
        cerr << '\n';
    }
    if (d[ducks.fi][ducks.se] < inf) {
        cout << ":)\n";
        while (ocean[ducks.fi][ducks.se] != 'x') {
            bool flag = true;
            fore(i, 0, 4) {
                if (ocean[ducks.fi][ducks.se] == currents[i]) {
                    flag = false;
//                    cerr << directions[i];
                    ducks.fi += t[i][0];
                    ducks.se += t[i][1];
                    break;
                }
            }
            if (flag) {
                int x, y;
                fore(i, 0, 4) {
                    x = ducks.fi + t[i][0];
                    y = ducks.se + t[i][1];
                    if (x < 0 || y < 0 || x >= r || y >= c || d[ducks.fi][ducks.se] != d[x][y] + 1)
                        continue;
                    cout << directions[i];
                    ducks = ii(x, y);
                    break;
                }
            }
        }
        cout << '\n';
    } else {
        puts(":(");
    }
    return 0;
}

Compilation message (stderr)

patkice.cpp: In function 'int main()':
patkice.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   52 |         freopen("main.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...