oj.uz

Submission #976093

# Submission time Handle Problem Language Result Execution time Memory
976093 2024-05-06T07:32:59 Z vjudge1 Awesome Arrowland Adventure (eJOI19_adventure) C++17
12 / 100
 1 ms 604 KB 
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair<int,pair<int,int>>
using namespace std;

char arr[505][505];
// 			   
map<char,int> dirx = {
	{'N', -1},
    {'E', 0},
    {'S', 1},
    {'W', 0},
};
map<char,int> diry = {
	{'N', 0},
    {'E', 1},
    {'S', 0},
    {'W', -1},
};
map <char,int> mp = {
    {'N', 0},
    {'E', 1},
    {'S', 2},
    {'W', 3},
};
vector<char> wheel(4);
bool vis[505][505];


signed main (){
	wheel = {'N','E','S','W'};
	int n,m; cin >> n >> m;
	for(int i = 0;i<n;i++){
		for(int j = 0;j<m;j++){
			cin >> arr[i][j];
		}
	}
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	pq.push({0,{0,0}});
	while(!pq.empty()){
		int d = pq.top().fi;
		int x = pq.top().se.fi;
		int y = pq.top().se.se;
		pq.pop();
		if(vis[x][y]) continue;
//		cout << d << " " << x << " " << y << endl;
		if(x == m-1 && y == n-1 && arr[x][y] == 'X'){
			cout << d << endl;
			return 0;
		}
		vis[x][y] = true;
		if(arr[x][y] == 'X') continue;
		for(auto &a:wheel){
			int add = (mp[a] - mp[arr[x][y]] + 4)%4;
//			cout << a << " " << add << endl;
			if(x + dirx[a] < 0 || y + diry[a] < 0 || y + diry[a] >= n || x + dirx[a] >= m ) continue;
			pq.push({d + add,{x + dirx[a],y + diry[a]}});
		}
//		cout << endl;
	}
	cout << "-1\n";
	
	return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

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