oj.uz

답안 #344780

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
344780 2021-01-06T14:18:53 Z jjj Awesome Arrowland Adventure (eJOI19_adventure) C++14
50 / 100
 2000 ms 18436 KB 
#include <bits/stdc++.h>
#define MAXN 510

using namespace std;

vector < vector <pair <int , int> > > g;
vector <string> s;

int p[MAXN * MAXN], d[MAXN * MAXN];

bool b[MAXN * MAXN];

void f(int n, int m)
{
	for(int i = 0; i < n * m; i++)
	{
		d[i] = -1;
		p[i] = -1;
	}
	
	d[0] = 0;
//	p[0] = 0;
	
	for(int i = 0; i <= n * m; i++)
	{
		int u = -1;
		
		for(int j = 0; j < n * m; j++)
			if(!b[j] && d[j] >= 0 && (u == -1 || d[j] < d[u])) u = j;
		
		if(u == -1) break;
		
		b[u] = true;
		
		int l = g[u].size();
		
		for(int j = 0; j < l; j++)
		{
			if(!b[g[u][j].first] && (d[g[u][j].first] == -1 || d[g[u][j].first] > d[u] + g[u][j].second))
			{
				d[g[u][j].first] =  d[u] + g[u][j].second;
				p[g[u][j].first] = u; 
			}
		}
	}
}

string c;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int n, m;
	
	cin >> n >> m;
	
	g.resize(n * m);
	
	for(int i = 0; i < n; i++)
	{
	 	cin >> c;
	 	
	 	s.push_back(c);
	}
	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			if(i < n - 1)
			{
				int k;
				
				if(s[i][j] != 'X')
				{
					if(s[i][j] == 'S') k = 0;
					if(s[i][j] == 'E') k = 1;
					if(s[i][j] == 'N') k = 2;
					if(s[i][j] == 'W') k = 3;
				
					g[i * m + j].push_back({(i + 1) * m + j, k});
				}
				
				if(s[i + 1][j] != 'X')
				{
					if(s[i + 1][j] == 'N') k = 0;
					if(s[i + 1][j] == 'W') k = 1;
					if(s[i + 1][j] == 'S') k = 2;
					if(s[i + 1][j] == 'E') k = 3;
					
					g[(i + 1) * m + j].push_back({i * m + j, k});
				}
			}
			
			if(j < m - 1)
			{
				int k;
				
				if(s[i][j] != 'X')
				{
					if(s[i][j] == 'E') k = 0;
					if(s[i][j] == 'N') k = 1;
					if(s[i][j] == 'W') k = 2;
					if(s[i][j] == 'S') k = 3;
				
					g[i * m + j].push_back({i * m + j + 1, k});
				}
				
				if(s[i][j + 1] != 'X')
				{
					if(s[i][j + 1] == 'W') k = 0;
					if(s[i][j + 1] == 'S') k = 1;
					if(s[i][j + 1] == 'E') k = 2;
					if(s[i][j + 1] == 'N') k = 3;
				
					g[i * m + j + 1].push_back({i * m + j, k});
				}
			}
		}
	}
	
	f(n, m);

/*	for(int i = 0; i <= n * m - 1; i++)
	{
		int l = g[i].size();
		
		for(int j = 0; j < l; j++) cout << "(" << g[i][j].first << ", " << g[i][j].second << ") ";
		
		cout << "\n"; 
	}

	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++) cout << d[i * m + j] << " ";
		
		cout << "\n";
	}
/*	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++) cout << p[i * m + j] << " ";
		
		cout << "\n";
	}
*/	
	cout << d[n * m - 1];
	
	return 0;
}

Compilation message

adventure.cpp:141:1: warning: "/*" within comment [-Wcomment]
  141 | /*
      |

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 492 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 364 KB Output is correct

Subtask #4
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #5
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 492 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Correct 1 ms 492 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 1 ms 364 KB Output is correct
32 Correct 1 ms 492 KB Output is correct
33 Correct 1 ms 364 KB Output is correct
34 Correct 1 ms 364 KB Output is correct
35 Correct 599 ms 2080 KB Output is correct
36 Correct 2 ms 492 KB Output is correct
37 Correct 845 ms 2344 KB Output is correct
38 Correct 8 ms 3308 KB Output is correct
39 Execution timed out 2079 ms 18436 KB Time limit exceeded
40 Halted 0 ms 0 KB -