Submission #1196179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196179		Ekber_Ekber	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	0 / 100	1 ms	2880 KiB

adventure

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define GOOD_LUCK ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
#define itn int
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define ppb pop_back
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define count1 __builtin_popcount
#define all(v) v.begin(), v.end()
#define pqueue priority_queue
using namespace std;
using namespace __gnu_pbds;

constexpr int MAX = 5e+2 + 3, INF = 2e+9, MOD = 1e+9 + 7, K = 31;

int temp, temp1, temp2, temp3;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
vector <vector <char>> v(MAX, vector <char>(MAX));
vector <vector <int>> dis(MAX, vector <int>(MAX, INF));

int get(char xx, int y) {
    int x;
    if (xx == 'X') return 1e+7;
    if (xx == 'N') x = 0;
    if (xx == 'E') x = 1;
    if (xx == 'S') x = 2;
    if (xx == 'W') x = 3;
    return (y >= x ? y - x : y - x + 4);
}

void dijkstra(int n, int m) {
    pqueue <pair<pair<int, int>, int>, vector <pair<pair<int, int>, int>>, greater<pair<pair<int, int>, int>>> pq;
    pq.push({{0, 0}, 0});
    dis[0][0]= 0;
    while (!pq.empty()) {
        auto x = pq.top();
        pq.pop();
        auto u = x.ff;
        int d = x.ss;
        if (dis[u.ff][u.ss] != d) continue;
        if (v[u.ff][u.ss] == 'X') continue;
        for (int j=0; j < 4; j++) {
            pair<int, int> i = {u.ff + dx[j], u.ss + dy[j]};
            if (i.ff < 0 || i.ff >= n || i.ss < 0 || i.ss >= m) continue;
            if (v[i.ff][i.ss] == 'X' && i.ff != n-1 && i.ss != m-1) continue;
            int g = get(v[u.ff][u.ss], j);
            if (dis[i.ff][i.ss] > dis[u.ff][u.ss] + g) {
                dis[i.ff][i.ss] = dis[u.ff][u.ss] + g;
                pq.push({i, dis[i.ff][i.ss]});
            }
        }
    }
}

vector <vector <char>> col(MAX, vector <char>(MAX, 0));

void dfs(int x, int y) {
    col[x][y] = 1;
    for (int i=0; i < 4; i++) {
        int ux = dx[i] + x, uy = dy[i] + y;
        if (!col[ux][uy]) dfs(ux, uy);
    }
}

void _() {
    int n, m;
    cin >> n >> m;
    dis.assign(n, vector <int>(m, INF));
    for (int i=0; i < n; i++) {
        for (int j=0; j < m; j++) {
            cin >> v[i][j];
        }
    }
    dfs(0, 0);
    if (!col[n-1][m-1]) {
        cout << -1;
        return;
    }
    dijkstra(n, m);
    cout << (dis[n-1][m-1] > n * m * 4 ? -1 : dis[n-1][m-1]);
}

signed main() {

	GOOD_LUCK

//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	freopen("log.txt", "w", stderr);
	srand(time(0));

	int tests=1;
//    cin >> tests;
	for (int i=1; i <= tests; i++) {
//		cout << "Case #" << i << ": "
		_();
//        cout << endl;
	}

//	int n;
//	while (cin >> n) {
//		_(n);
//		cout << endl;
//	}

	return 0;
}
// Problem X
// by Ekber_Ekber
/*
1
7
0100101

*/

Compilation message (stderr)

adventure.cpp: In function 'int main()':
adventure.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen("log.txt", "w", stderr);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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