oj.uz

Submission #787988

# Submission time Handle Problem Language Result Execution time Memory
787988 2023-07-19T15:51:01 Z Chal1shkan Awesome Arrowland Adventure (eJOI19_adventure) C++14
38 / 100
 1 ms 340 KB 
//Bismillahir-Rahmanir-Rahim

# include <bits/stdc++.h>
 
# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
# define all(x) (x).begin(), (x).end()
# define deb(x) cerr << #x  << " = " << x << endl; 
# define pll pair <ll, ll>
# define pii pair <int, int>
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
const ll maxn = 5e2 + 7;
const ll inf = 2e7 + 0;
const ll mod = 1e9 + 7;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, m;
char c[maxn][maxn];
int dist[maxn][maxn];

pii dir (char c)
{
	if (c == 'N') return {-1, 0};
	if (c == 'E') return {0, 1};
	if (c == 'S') return {1, 0};
	if (c == 'W') return {0, -1};
}

char f (pii p)
{
	if (p == make_pair(-1, 0)) return 'N';
	if (p == make_pair(0, 1)) return 'E';
	if (p == make_pair(1, 0)) return 'S';
	if (p == make_pair(0, -1)) return 'W';
}

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

int id (char c)
{
	if (c == 'N') return 0;
	if (c == 'E') return 1;
	if (c == 'S') return 2;
	if (c == 'W') return 3; 
}

int dst (char a, char b)
{
	int pos1 = id(a), pos2 = id(b);
	if (pos1 <= pos2) return pos2 - pos1;
	else return 4 - pos1 + pos2;
}

void ma1n (/* SABR */)
{
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			cin >> c[i][j];
			dist[i][j] = inf;
		}
	}
	set <pair <int, pii> > q;
	dist[1][1] = 0;
	q.insert({dist[1][1], {1, 1}});
//	for (char c : {'N', 'E', 'S', 'W'})
//	{
//		for (char b : {'N', 'E', 'S', 'W'})
//		{
//			cout << c << ' ' << b << ' ' << dst(c, b) << nl;
//		}
//	}
//	exit(0);
	while (!q.empty())
	{
		ll x = (q.begin() -> ss.ff);
		ll y = (q.begin() -> ss.ss);
		q.erase(q.begin());
	//	cout << x << ' ' << y << endl;
		if (x == n && y == m) continue;
		for (int k = 0; k < 4; ++k)
		{
			int add = dst(c[x][y], f({dx[k], dy[k]}));
			int nx = x + dx[k];
			int ny = y + dy[k];
			if (in(nx, ny) && dist[nx][ny] > dist[x][y] + add && (c[nx][ny] != 'X' || (nx == n && ny == m)))
			{
				dist[nx][ny] = dist[x][y] + add;
				q.insert({dist[nx][ny], {nx, ny}});
			}
		}
	}
//	for (int i = 1; i <= n; ++i)
//	{
//		for (int j = 1; j <= m; ++j)
//		{
//			cout << dist[i][j] << ' ';
//		}
//		cout << nl;
//	}
	if (dist[n][m] == inf)
	{
		cout << -1 << nl;
	}
	else
	{
		cout << dist[n][m] << nl;
	}
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//  freopen("file.in", "r", stdin);
//  freopen("file.out", "w", stdout);
    int ttt = 1;
//  cin >> ttt;
    for (int test = 1; test <= ttt; ++test)
    {
//      cout << "Case " << test << ":" << '\n';
        ma1n();
    }
    return 0;
}

// 998batrr | BbIWEJI 3A TObOU!!!
// tourist  | BbIWEJI 3A TObOU!!!

Compilation message

adventure.cpp: In function 'std::pair<int, int> dir(char)':
adventure.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
   38 | }
      | ^
adventure.cpp: In function 'char f(std::pair<int, int>)':
adventure.cpp:46:1: warning: control reaches end of non-void function [-Wreturn-type]
   46 | }
      | ^
adventure.cpp: In function 'int id(char)':
adventure.cpp:59:1: warning: control reaches end of non-void function [-Wreturn-type]
   59 | }
      | ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 332 KB Output is correct
20 Correct 1 ms 212 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 328 KB Output is correct

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 332 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Incorrect 0 ms 212 KB Output isn't correct
25 Halted 0 ms 0 KB -