oj.uz

Submission #785573

# Submission time Handle Problem Language Result Execution time Memory
785573 2023-07-17T10:19:14 Z alex_2008 Awesome Arrowland Adventure (eJOI19_adventure) C++14
12 / 100
 1 ms 468 KB 
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
using namespace std;
const int N = 550, INF = 1e9 + 10;
char a[N][N], vertex[N][N];
char dir[4] = { 'N', 'E', 'S', 'W' };
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int n, m;
bool ch(int x, int y) {
	if (x >= 1 && x <= n && y >= 1 && y <= m) return true;
	return false;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			vertex[i][j] = (i - 1) * m + j;
		}
	}
	vector <vector<pair<int, int>>> G(n * m + 1);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i][j] == 'X') continue;
			int ind = 0;
			for (int k = 0; k < 4; k++) {
				if (a[i][j] == dir[k]) {
					ind = k;
					break;
				}
			}
			int cost = 0;
			while (cost != 4) {
				if (ch(i + dx[ind], j + dy[ind])) {
					G[vertex[i][j]].push_back({ vertex[i + dx[ind]][j + dy[ind]], cost });
				}
				cost++;
				ind = (ind + 1) % 4;
			}
		}
	}
	vector <int> dist(n * m + 1, INF);
	dist[1] = 0;
	set <pair<int, int>> ms;
	ms.insert({ 0, 1 });
	while (!ms.empty()) {
		int v = ms.begin()->second; ms.erase(ms.begin());
		for (auto it : G[v]) {
			if (dist[v] + it.second < dist[it.first]) {
				auto k = ms.find({dist[it.first], it.first});
				if (k != ms.end()) {
					ms.erase(k);
				}
				dist[it.first] = dist[v] + it.second;
				ms.insert({ dist[it.first], it.first });
			}
		}
	}
	if (dist[n * m] == INF) {
		cout << -1 << "\n";
		return 0;
	}
	cout << dist[n * m] << "\n";
}

Subtask #1
0 / 10.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 Runtime error 1 ms 436 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
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 Runtime error 1 ms 436 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.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 Runtime error 1 ms 436 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -