Submission #467242

#	Time	Username	Problem	Language	Result	Execution time	Memory
467242		Stickfish	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	112 ms	3564 KiB

adventure

    #include <iostream>
    #include <complex>
    #include <set>
    using namespace std;
     
    const complex<int> IMAG(0, 1);
    const int MAXN = 501;
    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:61: 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: 16 / 16
• Subtask 5: 50 / 50