Submission #278443

#	Time	Username	Problem	Language	Result	Execution time	Memory
278443		acm	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	181 ms	49400 KiB

adventure

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

#define F first
#define S second 
#define mp make_pair
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define speed_up ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define sz(x) (int)x.size()
#define len(x) (int)strlen(x)
#define all(x) x.begin(), x.end()
#define debug cerr << "OK\n";
#define ub upper_bound
#define lb lower_bound 
 
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef set <int> si;
typedef set <ll> sll;
typedef multiset <int> msi;
typedef multiset <ll> msll;
typedef map <int, int> mi;
typedef map <ll, int> mll;
 
const int N = 1e3 + 2;
const int M = 3e5;
const int mod = 1e9 + 7;
const int inf = 2e9 + 3;
const ll INF = 1e16;

const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};

int n, m, d[N][N];
vector<int> a[N][N];

bool ok(int x, int y) {
	return x >= 1 && x <= n && y >= 1 && y <= m;
}

int main() {
	scanf("%d %d\n", &n, &m);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			d[i][j] = inf;
			char c;
			scanf("%c", &c);
			a[i][j].resize(4);
			if (c == 'W')
				a[i][j] = {1, 2, 3, 0};
			if (c == 'N')
				a[i][j] = {0, 1, 2, 3};				
			if (c == 'E')
				a[i][j] = {3, 0, 1, 2};
			if (c == 'S')
				a[i][j] = {2, 3, 0, 1};
			if (c == 'X')
				a[i][j] = {inf, inf, inf, inf};
		}
		scanf("\n");
	}
	d[1][1] = 0;
	set <pair<ll, pii>> s;
	s.insert({0, {1, 1}});
	while (!s.empty()) {
		int x = s.begin()->S.F;
		int y = s.begin()->S.S;
		int cost = s.begin()->F;
		s.erase(s.begin());
		for (int i = 0; i < 4; ++i) {
			if (ok(x + dx[i], y + dy[i]) && d[x + dx[i]][y + dy[i]] > cost + a[x][y][i]) {
				d[x + dx[i]][y + dy[i]] = cost + a[x][y][i];
				s.insert({d[x + dx[i]][y + dy[i]], {x + dx[i], y + dy[i]}});
			}				
		}
	}
	if (d[n][m] >= inf)
		d[n][m] = -1;
	printf("%d\n", d[n][m]);
		
}

Compilation message (stderr)

adventure.cpp: In function 'int main()':
adventure.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |  scanf("%d %d\n", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
adventure.cpp:56:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |    scanf("%c", &c);
      |    ~~~~~^~~~~~~~~~
adventure.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |   scanf("\n");
      |   ~~~~~^~~~~~

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