oj.uz

Submission #1018910

# Submission time Handle Problem Language Result Execution time Memory
1018910 2024-07-10T10:48:42 Z mar Awesome Arrowland Adventure (eJOI19_adventure) C++14
12 / 100
 1 ms 604 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
#define pii pair<int,pair<int,int>>
 
 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 visited[505][505];
 int n,m;
 bool flag=0;

void bfs(){
    priority_queue<pii,vector<pii>,greater<pii>> pq;
	pq.push({0,{0,0}});
	while(!pq.empty()){
		int d = pq.top().f;
		int x = pq.top().s.f;
		int y = pq.top().s.s;
		pq.pop();
		if(visited[x][y]) continue;
		
		if(x == m-1 && y == n-1){
			cout << d << endl;
			flag=1;
			return;
		}
		visited[x][y] = true;
		if(arr[x][y] == 'X') continue;
		for(auto &a:wheel){
			int add = (mp[a] - mp[arr[x][y]] +4)%4;
			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;
	}
}
 
int main (){
	wheel = {'N','E','S','W'};
	 cin >> n >> m;
	for(int i = 0;i<n;i++){
		for(int j = 0;j<m;j++){
			cin >> arr[i][j];
		}
	}
	bfs();
	if(!flag)cout << "-1\n";
	
	return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 604 KB Output isn't correct
2 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 0 ms 348 KB Output is correct

Subtask #4
0 / 16.0

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

Subtask #5
0 / 50.0

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