Submission #229759

#	Time	Username	Problem	Language	Result	Execution time	Memory
229759		Coder	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	129 ms	17612 KiB

adventure

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define SZ(x) (int)(x.size())
#define F0(i,n) for(int i=0;i<n;i++)
#define F1(i,n) for(int i=1;i<=n;i++)
#define CL(a,x) memset(x, a, sizeof(x));
#define PR(x) cerr << #x << "=" << (x) << endl;
const int MOD = 1000000007;
const double pi = atan(1.0)*4.0;
const double eps = 1e-8;
const int N = 501;
int i, j, k, m, n;
int a[N];


string s[N];
int DX[]={-1,0,1,0};
int DY[]={0,1,0,-1};
int d[N][N];
string H="NESW";
int main() {
    //freopen("x.in", "r", stdin);

    cin >> m >> n;
    F0(i, m) cin >> s[i];

    set<pair<int, pii>> S;
    CL(-1, d);
    d[0][0] = 0;
    S.insert(make_pair(0, pii(0, 0)));
    while (!S.empty()) {
        pii p = S.begin()->second;
        S.erase(S.begin());
        if (s[p.first][p.second] == 'X') continue;
        F0(k, 4) {
            int x = p.first + DX[k], y = p.second + DY[k];
            if (x < 0 || x >= m || y < 0 || y >= n) continue;

            int d0 = H.find(s[p.first][p.second]);
            int cost = (k - d0 + 4) % 4 + d[p.first][p.second];

            if (d[x][y] == -1 || d[x][y] > cost) {
                d[x][y] = cost;
                S.insert(make_pair(cost, pii(x, y)));
            }
        }
    }
    cout << d[m-1][n-1] << endl;

    return 0;
}

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