Submission #697451

#	Time	Username	Problem	Language	Result	Execution time	Memory
697451		aklo	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	91 ms	17308 KiB

adventure

#include <bits/stdc++.h>

using namespace std;

const int N = 505;
int n, m, b;
char a[N][N];
set <pair <int, pair <int,int> > > s;
char slj[10] = {'N', 'E', 'S', 'W', 'N', 'E', 'S', 'W'};

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};


int main(){
	
	cin >> n >> m;
	
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			cin >> a[i][j];
		}
 	}
 	
 	s.insert({0,{0,0}});
 	int dist[N][N];
 	memset(dist, -1, sizeof(dist));
 	while (s.size() > 0){
 		//cout<<"\n";
 		//cout<<s.begin()->first<<" "<<s.begin()->second.first<<" "<<s.begin()->second.second<<"\n";
 		int x = s.begin()->second.first;
 		int y = s.begin()->second.second;
 		b=s.begin()->first;
 		s.erase(s.begin());
 		if(dist[x][y]!=-1) continue;
 		dist[x][y] = b;
 		if(a[x][y]=='X') continue;
 		//cout<<x<<" "<<y<<" "<<dist[x][y]<<"\n";
 		for (int i = 0; i < 4; i++){
 			int nx = x + dx[i];
 			int ny = y + dy[i];
 			//if(x==0 && y==0) cout<<nx<<" a "<<ny<<" "<<dist[nx][ny]<<"\n";
 			if (nx >= n or ny >= m) continue;
 			if (nx < 0 or ny < 0) continue;
 			if (dist[nx][ny] != -1) continue;
			
			int ud = 0;
			bool p = 0;
			for (int j = 0; j < 4; j++){
				if (p) break;
				if (a[x][y] == slj[j]){
					for (int k = j; k < 8; k++){
						if (slj[k] == slj[i]) p = 1;
						if (p) break;
						ud++;
					}
				}	
		 	}
		 	//cout<<dist[x][y]+ud<<" "<<nx<<" "<<ny<<"\n";
		 	
		 	s.insert({dist[x][y] + ud,{nx,ny}});
		}
	}
	
	cout << dist[n-1][m-1];
	
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 16 / 16
• Subtask 5: 50 / 50