Submission #284351

#	Time	Username	Problem	Language	Result	Execution time	Memory
284351		antontsiorvas	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	50 / 100	2093 ms	2020 KiB

adventure

#include <cstdio>
#include <climits>

int rows, cols, dist[505][505], cnt, point[2];
bool visited[505][505];
char data[505][505];

int find_rots(char a, char b){
	if(a == 'N'){
		if(b == 'N') return 0;
		if(b == 'E') return 1;
		if(b == 'S') return 2;
		if(b == 'W') return 3;
	}
	if(a == 'E'){
		if(b == 'N') return 3;
		if(b == 'E') return 0;
		if(b == 'S') return 1;
		if(b == 'W') return 2;
	}
	if(a == 'S'){
		if(b == 'N') return 2;
		if(b == 'E') return 3;
		if(b == 'S') return 0;
		if(b == 'W') return 1;
	}
	if(a == 'W'){
		if(b == 'N') return 1;
		if(b == 'E') return 2;
		if(b == 'S') return 3;
		if(b == 'W') return 0;
	}
	return 0;
}

void find_min(){
	int minimum = INT_MAX-1;
	point[0] = point[1] = -1;
	for(int i=0; i<rows; i++){
		for(int j=0; j<cols; j++){
			if(!visited[i][j] && minimum > dist[i][j]){
				point[0] = i;
				point[1] = j;
				minimum = dist[i][j];
			}
		}
	}
}

bool isWithinBounds(int r, int c){	return 0 <= r && r < rows && 0 <= c && c < cols;	}

int dijkstra(){
	for(int i=0; i<rows; i++){
		for(int j=0; j<cols; j++){
			dist[i][j] = INT_MAX; 
			if(data[i][j] == 'X') visited[i][j] = true;
		}
	}
	dist[0][0] = 0;
	int points = rows*cols;
	while(cnt < points && !visited[rows-1][cols-1]){
		find_min();
		if(point[0] == -1) return INT_MAX;
		int row = point[0], col = point[1];
		visited[row][col] = true;
		cnt++;
		if(isWithinBounds(row-1,col) && !visited[row-1][col] && dist[row][col]+find_rots(data[row][col],'N') < dist[row-1][col]){
			dist[row-1][col] = dist[row][col]+find_rots(data[row][col],'N');
		}
		if(isWithinBounds(row+1,col) && !visited[row+1][col] && dist[row][col]+find_rots(data[row][col],'S') < dist[row+1][col]){
			dist[row+1][col] = dist[row][col]+find_rots(data[row][col],'S');
		}
		if(isWithinBounds(row,col-1) && !visited[row][col-1] && dist[row][col]+find_rots(data[row][col],'W') < dist[row][col-1]){
			dist[row][col-1] = dist[row][col]+find_rots(data[row][col],'W');
		}
		if(isWithinBounds(row,col+1) && !visited[row][col+1] && dist[row][col]+find_rots(data[row][col],'E') < dist[row][col+1]){
			dist[row][col+1] = dist[row][col]+find_rots(data[row][col],'E');
		}
	}
	return dist[rows-1][cols-1];
}

int main(){
	scanf("%d%d",&rows,&cols);
	for(int i=0; i<rows; i++) scanf("\n%s",data[i]);
	data[rows-1][cols-1] = 'F';
	int ans = dijkstra();
	if(ans == INT_MAX) printf("-1");
	else printf("%d",ans);
}

Compilation message (stderr)

adventure.cpp: In function 'int main()':
adventure.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |  scanf("%d%d",&rows,&cols);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~
adventure.cpp:85:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |  for(int i=0; i<rows; i++) scanf("\n%s",data[i]);
      |                            ~~~~~^~~~~~~~~~~~~~~~

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