Submission #467240

#	Time	Username	Problem	Language	Result	Execution time	Memory
467240		Stickfish	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	34 / 100	1 ms	292 KiB

adventure

#include <iostream>
#include <complex>
#include <set>
using namespace std;

const complex<int> IMAG(0, 1);
const int MAXN = 101;
const int INF = 1e9;
complex<int> f[MAXN][MAXN];
int dp[MAXN][MAXN];

bool operator<(const complex<int>& c1, const complex<int>& c2){
	return c1.real() < c2.real() || c1.real() == c2.real() && c1.imag() < c2.imag();
}

struct ccomporator{
	bool operator()(const pair<int, complex<int>> p1, const pair<int, complex<int>> p2) const {
		if(p1.first < p2.first)
			return true;
		if(p1.first > p2.first)
			return false;
		if(p1.second.real() < p2.second.real())
			return true;
		if(p1.second.real() > p2.second.real())
			return false;
		if(p1.second.imag() < p2.second.imag())
			return true;
		return false;

	}
};


signed main(){
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < m; ++j){
			char c;
			cin >> c;
			if(c == 'E'){
				f[i][j] = IMAG;
			} else if(c == 'N'){
				f[i][j] = -1;
			} else if(c == 'S'){
				f[i][j] = 1;
			} else if(c == 'W'){
				f[i][j] = -IMAG;
			} else {
				f[i][j] = 0;
			}
			dp[i][j] = INF;
		}
	}
	dp[0][0] = 0;
	set<pair<int, complex<int>>, ccomporator> st;
	st.insert({0, 0});
	while(st.size()){
		complex<int> pt = st.begin()->second;
		st.erase(st.begin());
		for(complex<int> timer = 0, mv = f[pt.real()][pt.imag()]; timer != 4; timer += 1, mv *= -IMAG){
			complex<int> npt = pt + mv;
			if(0 <= npt.real() && npt.real() < n && 0 <= npt.imag() && npt.imag() < m && dp[npt.real()][npt.imag()] > dp[pt.real()][pt.imag()]){
				st.erase({dp[npt.real()][npt.imag()], npt});
				dp[npt.real()][npt.imag()] = min(dp[npt.real()][npt.imag()], dp[pt.real()][pt.imag()] + timer.real());
				st.insert({dp[npt.real()][npt.imag()], npt});
			}
		}
	}
	if(dp[n - 1][m - 1] == INF){
		cout << -1 << endl;
	} else {
		cout << dp[n - 1][m - 1] << endl;
	}
}

Compilation message (stderr)

adventure.cpp: In function 'bool operator<(const std::complex<int>&, const std::complex<int>&)':
adventure.cpp:13:57: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   13 |  return c1.real() < c2.real() || c1.real() == c2.real() && c1.imag() < c2.imag();
      |                                  ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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