Submission #641892

#	Time	Username	Problem	Language	Result	Execution time	Memory
641892		Nelt	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	461 ms	15640 KiB

adventure

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
// #include <ext/pb_ds/detail/standard_policies.hpp>
// #include <windows.h>

/* DEFINES */
#define S second
#define F first
#define ll long long
#define ull unsigned long long
#define ld long double
#define npos ULLONG_MAX
#define INF LLONG_MAX
#define elif else if
#define vv(a) vector<a>
#define pp(a, b) pair<a, b>
#define pq(a) priority_queue<a>
#define qq(a) queue<a>
#define ss(a) set<a>
#define mm(a, b) map<a, b>
#define ump(a, b) unordered_map<a, b>
#define pb push_back
#define sync                      \
    ios_base::sync_with_stdio(0); \
    cin.tie();                    \
    cout.tie();
#define endl "\n"
#define allc(a) begin(a), end(a)
#define all(a) a, a + sizeof(a) / sizeof(a[0])
#define mpr make_pair
#define ins insert
using namespace std;
using namespace __cxx11;
typedef char chr;
typedef basic_string<chr> str;
const int sz = 505;
int n, m, g[sz][sz], d[sz][sz];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int num[] = {3, 1, 2, 4};
bool can_go(int x, int y)
{
    return (x >= 1 and y >= 1 and x <= n and y <= m);
}
int x, y, c, x2, y2, cnt = 1, cnt1[4];
qq(pp(int, int)) q[4];
void bfs(int sx, int sy)
{
    for (ll i = 1; i <= n; i++)
        fill(d[i], d[i] + m + 1, 1e9);
    d[sx][sy] = 0;
    q[0].push(mpr(sx, sy));
    cnt1[0] = 1;
    while (cnt--)
    {
        pp(int, int) cord;
        for (int i = 0; i < 4; i++)
            if (cnt1[i])
            {
                cord = q[i].front();
                q[i].pop();
                cnt1[i]--;
                break;
            }
        x = cord.F, y = cord.S;
        if (g[x][y] == -1)
            continue;
        for (int k = 0; k < 4; k++)
        {
            c = num[k] - g[x][y];
            c += (c < 0 ? 4 : 0);
            x2 = x + dx[k], y2 = y + dy[k];
            (can_go(x2, y2) && d[x2][y2] > d[x][y] + c) ? q[c].push(mpr(x2, y2)),
                cnt++, cnt1[c]++,
                d[x2][y2] = d[x][y] + c : 0;
        }
    }
}
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        chr s[m];
        scanf("%s\n", s);
        for (int j = 0; j < m; j++)
        {
            g[i][j + 1] = (s[j] == 'N' ? 1 : s[j] == 'E' ? 2
                                         : s[j] == 'S'   ? 3
                                         : s[j] == 'W'   ? 4
                                                         : -1);
        }
    }
    bfs(1, 1);
    cout << (d[n][m] == 1e9 ? -1 : d[n][m]) << endl;
}
/*

*/
int main()
{
    // sync
    // precomp();
    ll t = 1;
    // cin >> t;
    for (ll i = 1; i <= t; i++)
        // cout << "Case #" << i << ": ",
        solve();
    cerr << "\nTime elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

Compilation message (stderr)

adventure.cpp: In function 'void solve()':
adventure.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         scanf("%s\n", s);
      |         ~~~~~^~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 16 / 16
• Subtask 5: 50 / 50