oj.uz

Submission #1090244

# Submission time Handle Problem Language Result Execution time Memory
1090244 2024-09-18T05:43:53 Z Muhammet Awesome Arrowland Adventure (eJOI19_adventure) C++17
38 / 100
 1 ms 608 KB 
#include <bits/stdc++.h>

using namespace std;

#define ff first
#define ss second

int n, m, vis[505][505];

char v[] = {'N', 'E', 'S', 'W'};

vector <vector <char>> a;

vector <vector <int>> dp;

int f(char x, char y){
	int ind = 0;
	for(int i = 0; i < 4; i++){
		if(v[i] == x){
			ind = i;
			break;
		}
	}
	int cnt = 0;
	while(1){
		if(v[ind] == y) break;
		ind++;
		if(ind == 4) ind = 0;
		cnt++;
	}
	return cnt;
}

int main(){
	cin >> n >> m;
	a.assign(n+1, vector <char> (m+1));
	dp.assign(n+1, vector <int> (m+1,1e9));
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
		}
	}
	priority_queue <pair<int,pair<int,int>>> q;
	q.push({0,{n,m}});
	for(int i = 0; i <= n+1; i++){
		vis[i][0] = vis[i][m+1] = 1;
	}
	for(int i = 0; i <= m+1; i++){
		vis[0][i] = vis[n+1][i] = 1;
	}
	dp[n][m] = 0;
	a[n][m] = 'E';
	vis[n][m] = 1;
	while(!q.empty()){
		int i = q.top().ss.ff;
		int j = q.top().ss.ss;
		int w = q.top().ff;
		if(i == 1 and j == 1) break;
		// cout << i << ' ' << j << ' ' dp[i][j] << '\n';
		w *= (-1);
		q.pop();
		if((a[i][j] == 'X') or (dp[i][j] != w)) continue;
		if(vis[i][j+1] == 0 and f(a[i][j+1],'W')+dp[i][j] < dp[i][j+1]){
			dp[i][j+1] = f(a[i][j+1],'W')+dp[i][j];
			q.push({-dp[i][j+1],{i,j+1}});
		}
		if(vis[i][j-1] == 0 and f(a[i][j-1],'E')+dp[i][j] < dp[i][j-1]){
			dp[i][j-1] = f(a[i][j-1],'E')+dp[i][j];
			q.push({-dp[i][j-1],{i,j-1}});
		}
		if(vis[i+1][j] == 0 and f(a[i+1][j],'N')+dp[i][j] < dp[i+1][j]){
			dp[i+1][j] = f(a[i+1][j],'N')+dp[i][j];
			q.push({-dp[i+1][j],{i+1,j}});
		}
		if(vis[i-1][j] == 0 and f(a[i-1][j],'S')+dp[i][j] < dp[i-1][j]){
			dp[i-1][j] = f(a[i-1][j],'S')+dp[i][j];
			q.push({-dp[i-1][j],{i-1,j}});
		}
	}
	cout << (dp[1][1] == 1e9 ? -1 : dp[1][1]);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 360 KB Output is correct
2 Correct 0 ms 360 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Incorrect 0 ms 360 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 0 ms 360 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 1 ms 360 KB Output is correct
5 Correct 0 ms 360 KB Output is correct
6 Correct 0 ms 360 KB Output is correct
7 Correct 0 ms 360 KB Output is correct
8 Correct 0 ms 360 KB Output is correct
9 Correct 0 ms 360 KB Output is correct
10 Correct 0 ms 360 KB Output is correct

Subtask #5
0 / 50.0

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