답안 #467240

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
467240	2021-08-22T08:14:53 Z	Stickfish	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	34 / 100	1 ms	292 KB

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

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.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	292 KB	Output is correct
10	Correct	1 ms	292 KB	Output is correct

Subtask #2

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	292 KB	Output is correct
10	Correct	1 ms	292 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	204 KB	Output is correct

Subtask #3

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct

Subtask #4

0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	292 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Incorrect	1 ms	204 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #5

0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	292 KB	Output is correct
10	Correct	1 ms	292 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	204 KB	Output is correct
21	Correct	1 ms	204 KB	Output is correct
22	Correct	0 ms	204 KB	Output is correct
23	Correct	0 ms	204 KB	Output is correct
24	Correct	0 ms	204 KB	Output is correct
25	Correct	1 ms	292 KB	Output is correct
26	Correct	1 ms	204 KB	Output is correct
27	Incorrect	1 ms	204 KB	Output isn't correct
28	Halted	0 ms	0 KB	-