oj.uz

Submission #284351

# Submission time Handle Problem Language Result Execution time Memory
284351 2020-08-27T09:11:13 Z antontsiorvas Awesome Arrowland Adventure (eJOI19_adventure) C++14
50 / 100
 2000 ms 2020 KB 
#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

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.0 / 10.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 1 ms 256 KB Output is correct
19 Correct 1 ms 256 KB Output is correct
20 Correct 1 ms 256 KB Output is correct
21 Correct 1 ms 256 KB Output is correct
22 Correct 1 ms 256 KB Output is correct
23 Correct 1 ms 256 KB Output is correct
24 Correct 0 ms 256 KB Output is correct
25 Correct 1 ms 256 KB Output is correct
26 Correct 0 ms 256 KB Output is correct
27 Correct 1 ms 256 KB Output is correct
28 Correct 1 ms 256 KB Output is correct
29 Correct 2 ms 256 KB Output is correct
30 Correct 1 ms 256 KB Output is correct
31 Correct 1 ms 256 KB Output is correct
32 Correct 0 ms 256 KB Output is correct
33 Correct 0 ms 256 KB Output is correct
34 Correct 1 ms 256 KB Output is correct
35 Correct 1240 ms 512 KB Output is correct
36 Correct 1 ms 384 KB Output is correct
37 Correct 1641 ms 640 KB Output is correct
38 Correct 1 ms 1152 KB Output is correct
39 Execution timed out 2093 ms 2020 KB Time limit exceeded
40 Halted 0 ms 0 KB -