답안 #122400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
122400	2019-06-28T07:11:39 Z	김세빈(#2988)	로봇 (APIO13_robots)	C++14	컴파일 오류	0 ms	0 KB

robots

#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 pritnf("-1\n");
	
	return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:159:7: error: 'pritnf' was not declared in this scope
  else pritnf("-1\n");
       ^~~~~~
robots.cpp:159:7: note: suggested alternative: 'printf'
  else pritnf("-1\n");
       ^~~~~~
       printf
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]);
   ~~~~~^~~~~~~~~~~~