oj.uz

Submission #823607

# Submission time Handle Problem Language Result Execution time Memory
823607 2023-08-12T20:51:58 Z ThylOne Awesome Arrowland Adventure (eJOI19_adventure) C++14
100 / 100
 36 ms 4212 KB 
#include<bits/stdc++.h>


using namespace std;
int dir[4][2] ={
	{0,-1}, //N
	{1,0}, // E
	{0,1},//  S
	{-1,0}//  W
};
#define X -1
int val(char C){
	if(C=='N')return 0;
	if(C=='E')return 1;
	if(C=='S')return 2;
	if(C=='W')return 3;
	return X;
};
struct node{
	int x,y,cost;
};
bool operator<(node a,node b){
	return a.cost>b.cost;
}
int width,height;
bool in(int x,int y){
	return (x>=0 && y>=0 && x<width && y<height);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>height>>width;
	char tab[width][height];
	bool mem[width][height];
	for(int y=0;y<height;y++){
		string line;cin>>line;
		for(int x=0;x<width;x++){
			mem[x][y] = false;
			tab[x][y] = line[x];
		}
		
	}
	priority_queue<node> PQ;
	PQ.push({0,0,0});

	while(!PQ.empty()){
		
		node act = PQ.top();PQ.pop();
		if(mem[act.x][act.y])continue;
		mem[act.x][act.y]=true;
		
		
		int direction = val(tab[act.x][act.y]);
		//On jette les croix
		if(act.x==width-1 && act.y==height-1){
			cout<<act.cost<<endl;
			return 0;
		}
		if(direction==X)continue;
		for(int d=0;d<4;d++){
			
			int D = (direction+d)%4;
			//On calcul les voisins
			int vx = act.x + dir[D][0];
			int vy = act.y + dir[D][1];
			
			if(in(vx,vy) && !mem[vx][vy]){
				PQ.push({vx,vy,act.cost+d});
			}
		}
	}
	cout<<-1<<endl;
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 320 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 320 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 260 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 320 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 0 ms 316 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 0 ms 316 KB Output is correct
32 Correct 1 ms 292 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 3 ms 340 KB Output is correct
36 Correct 0 ms 324 KB Output is correct
37 Correct 3 ms 324 KB Output is correct
38 Correct 0 ms 340 KB Output is correct
39 Correct 33 ms 1120 KB Output is correct
40 Correct 34 ms 1100 KB Output is correct
41 Correct 1 ms 968 KB Output is correct
42 Correct 36 ms 1100 KB Output is correct
43 Correct 34 ms 4212 KB Output is correct
44 Correct 1 ms 964 KB Output is correct