Submission #823607

#	Time	Username	Problem	Language	Result	Execution time	Memory
823607		ThylOne	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	36 ms	4212 KiB

adventure

#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 / 10
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 16 / 16
• Subtask 5: 50 / 50