oj.uz

답안 #122401

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122401 2019-06-28T07:12:40 Z 김세빈(#2988) 로봇 (APIO13_robots) C++14
60 / 100
 1500 ms 84960 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;

vector <int> V[303030], X[303030];
queue <pii> Q;
char S[555][555];
int chk[555][555][4];
int vis[303030];
int dp[303030][55];
int _N[10][10], _X[55], _Y[55];
int n, m, k, cnt, ans;

int dfs(int x, int y, int d)
{
	if(chk[x][y][d] >= 0) return chk[x][y][d];
	else if(chk[x][y][d] == -1) return -1;
	
	chk[x][y][d] = -1;
	
	int ret, _d;
	
	if(S[x][y] == 'A') _d = (d + 1) % 4;
	else if(S[x][y] == 'C') _d = (d + 3) % 4;
	else _d = d;
	
	if(_d == 0){
		if(x == n - 1 || S[x + 1][y] == 'x') ret = x * m + y;
		else ret = dfs(x + 1, y, _d);
	}
	else if(_d == 1){
		if(y == m - 1 || S[x][y + 1] == 'x') ret = x * m + y;
		else ret = dfs(x, y + 1, _d);
	}
	else if(_d == 2){
		if(x == 0 || S[x - 1][y] == 'x') ret = x * m + y;
		else ret = dfs(x - 1, y, _d);
	}
	else{
		if(y == 0 || S[x][y - 1] == 'x') ret = x * m + y;
		else ret = dfs(x, y - 1, _d);
	}
	
	return chk[x][y][d] = ret;
}

int main()
{
	int i, j, l, s;
	
	scanf("%d%d%d", &k, &m, &n);
	
	s = 0;
	
	for(i=1; i<=k; i++){
		for(j=i; j>=1; j--){
			_N[i][j] = s;
			_X[s] = i; _Y[s] = j;
			s ++;
		}
	}
	
	for(i=0; i<n; i++){
		scanf("%s", S[i]);
		for(j=0; j<m; j++){
			for(l=0; l<4; l++){
				chk[i][j][l] = -2;
			}
			
			for(l=0; l<k*(k+1)/2; l++){
				dp[i * m + j][l] = 1e9;
			}
			
			if('1' <= S[i][j] && S[i][j] <= '0' + k){
				dp[i * m + j][(int)(S[i][j] - '0') * (S[i][j] - '0' - 1) / 2] = 0;
			}
		}
	}
	
	for(i=0; i<n; i++){
		for(j=0; j<m; j++){
			for(l=0; l<4; l++){
				if(dfs(i, j, l) != -1 && dfs(i, j, l) != i * m + j){
					V[i * m + j].push_back(dfs(i, j, l));
				}
			}
		}
	}
	
	for(i=0; i<k*(k+1)/2; i++){
		int v = 1e9;
		for(j=0; j<n; j++){
			for(l=0; l<m; l++){
				v = min(v, dp[j * m + l][i]);
			}
		}
		if(v == 1e9) continue;
		
		for(j=0; j<n; j++){
			for(l=0; l<m; l++){
				if(dp[j * m + l][i] < v + n * m){
					X[dp[j * m + l][i] - v].push_back(j * m + l);
				}
			}
		}
		
		cnt ++; for(; !Q.empty(); Q.pop());
		
		for(j=0; j<n*m; j++){
			for(int &t: X[j]) if(vis[t] != cnt){
				vis[t] = cnt;
				Q.push(pii(t, j));
			}
			X[j].clear();
			
			for(; !Q.empty() && Q.front().second == j;){
				int p = Q.front().first; Q.pop();
				dp[p][i] = j + v;
				for(int &t: V[p]) if(vis[t] != cnt){
					Q.push(pii(t, j + 1));
					vis[t] = cnt;
				}
			}
		}
		
		int x = _X[i], y = _Y[i], z;
		
		for(j=0; j<n; j++){
			for(l=0; l<m; l++){
				int id = j * m + l;
				for(z=y-1; z>=1; z--){
					dp[id][_N[x][z]] = min(dp[id][_N[x][z]], dp[id][_N[y - 1][z]] + dp[id][i]);
				}
			}
		}
/*		
		printf("%d %d\n", y, x);
		for(j=0; j<n; j++){
			for(l=0; l<m; l++){
				if(dp[j * m + l][i] == 1e9) printf("  .");
				else printf("%3d", dp[j * m + l][i]);
			}
			printf("\n");
		}
		printf("\n");
*/	}
	
	ans = 1e9;
	
	for(i=0; i<n; i++){
		for(j=0; j<m; j++){
			ans = min(ans, dp[i * m + j][k * (k + 1) / 2 - 1]);
		}
	}
	
	if(ans < 1e9) printf("%d\n", ans);
	else printf("-1\n");
	
	return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &k, &m, &n);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", S[i]);
   ~~~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 14592 KB Output is correct
2 Correct 14 ms 14592 KB Output is correct
3 Correct 14 ms 14592 KB Output is correct
4 Correct 14 ms 14720 KB Output is correct
5 Correct 14 ms 14720 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 14592 KB Output is correct
2 Correct 14 ms 14592 KB Output is correct
3 Correct 14 ms 14592 KB Output is correct
4 Correct 14 ms 14720 KB Output is correct
5 Correct 14 ms 14720 KB Output is correct
6 Correct 13 ms 14592 KB Output is correct
7 Correct 13 ms 14592 KB Output is correct
8 Correct 14 ms 14592 KB Output is correct
9 Correct 14 ms 14592 KB Output is correct
10 Correct 13 ms 14572 KB Output is correct
11 Correct 257 ms 39768 KB Output is correct
12 Correct 51 ms 39160 KB Output is correct
13 Correct 120 ms 39672 KB Output is correct
14 Correct 414 ms 40576 KB Output is correct
15 Correct 155 ms 39732 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 14592 KB Output is correct
2 Correct 14 ms 14592 KB Output is correct
3 Correct 14 ms 14592 KB Output is correct
4 Correct 14 ms 14720 KB Output is correct
5 Correct 14 ms 14720 KB Output is correct
6 Correct 13 ms 14592 KB Output is correct
7 Correct 13 ms 14592 KB Output is correct
8 Correct 14 ms 14592 KB Output is correct
9 Correct 14 ms 14592 KB Output is correct
10 Correct 13 ms 14572 KB Output is correct
11 Correct 257 ms 39768 KB Output is correct
12 Correct 51 ms 39160 KB Output is correct
13 Correct 120 ms 39672 KB Output is correct
14 Correct 414 ms 40576 KB Output is correct
15 Correct 155 ms 39732 KB Output is correct
16 Correct 786 ms 81700 KB Output is correct
17 Execution timed out 1571 ms 84960 KB Time limit exceeded
18 Halted 0 ms 0 KB -