oj.uz

답안 #122353

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122353 2019-06-28T05:25:32 Z 이온조(#2989) 로봇 (APIO13_robots) C++14
60 / 100
 1500 ms 136268 KB 
#include <cstdio>
#include <algorithm>
#include <queue>
#include <tuple>
#include <set>
#pragma GCC optimize ("Ofast")
using namespace std;
using pii = pair<int, int>;

struct node {
	int x, y, s, e;
};

const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};

char A[509][509];
int D[501][501][10][10];
pii E[501][501][4];
bool vs[501][501][10][10];
vector<node> S[250009];

pii go(int x, int y, int dir) {
	int xx = x, yy = y, dd = dir;
	if(E[x][y][dir] != (pii){0, 0}) return E[x][y][dir];
	set<pii> chk;
	while(1) {
		if(chk.find({x, y}) != chk.end()) return E[xx][yy][dd] = {xx, yy};
		chk.insert({x, y});
		// printf("in go:  x: %d, y: %d, dir: %d\n", x, y, dir);
		if(A[x][y] == 'A') dir += 3, dir %= 4;
		if(A[x][y] == 'C') dir += 1, dir %= 4;
		int X = x + dx[dir], Y = y + dy[dir];
		if(A[X][Y] == 'x') break;
		x = X; y = Y;
	}
	// puts("done");
	return E[xx][yy][dd] = {x, y};
}

inline void mark(node X, int dist) {
	int a = X.x, b = X.y, c = X.s, d = X.e;
	vs[a][b][c][d] = 1; D[a][b][c][d] = dist;
}

int main() {
	int N, W, H; scanf("%d%d%d",&N,&W,&H);
	for(int i=0; i<=H+1; i++) for(int j=0; j<=W+1; j++) A[i][j] = 'x';
	for(int i=1; i<=H; i++) {
		for(int j=1; j<=W; j++) {
			scanf(" %c", &A[i][j]);
			if('1' <= A[i][j] && A[i][j] <= '9') {
				int id = A[i][j] - '0';
				S[0].push_back({i, j, id, id});
			}
		}
	}
	int sum = 0;
	queue<node> que;
	for(int i=1; i<=N; i++) {
		int c = 0;
		do {
			for(auto& it: S[c]) if(!vs[it.x][it.y][it.s][it.e] && it.e - it.s + 1 == i) {
				que.push(it);
				mark(it, sum + c);
			}
			while(S[c].size()) S[c].pop_back();
			int sz = que.size();
			while(sz--) {
				node P = que.front(); que.pop();
				// printf("i: %d, dist: %d, x: %d, y: %d, s: %d, e: %d\n", i, sum + c, P.x, P.y, P.s, P.e);
				for(int k=0; k<4; k++) {
					int X, Y; tie(X, Y) = go(P.x, P.y, k);
					// printf("X: %d, Y: %d\n", X, Y);
					if(!vs[X][Y][P.s][P.e]) {
						que.push({X, Y, P.s, P.e});
						mark({X, Y, P.s, P.e}, sum + c + 1);
					}
				}
			}
			++c;
		} while(que.size());

		if(i == N) break;
		// puts("CALCULATE START");
		int gmn = 1e9;
		for(int p=1; p<=H; p++) {
			for(int q=1; q<=W; q++) {
				for(int j=i+1; j<=N; j++) {
					for(int k=j-i; k<j; k++) {
						if(vs[p][q][j-i][k] && vs[p][q][k+1][j]) {
							gmn = min(gmn, D[p][q][j-i][k] + D[p][q][k+1][j]);
						}
					}
				}
			}
		}
		for(int p=1; p<=H; p++) {
			for(int q=1; q<=W; q++) {
				for(int j=i+1; j<=N; j++) {
					int mn = 1e9;
					for(int k=j-i; k<j; k++) {
						if(vs[p][q][j-i][k] && vs[p][q][k+1][j]) {
							mn = min(mn, D[p][q][j-i][k] + D[p][q][k+1][j]);
						}
					}
					if(mn != 1e9) S[mn - gmn].push_back({p, q, j-i, j});
				}
			}
		}
		sum = gmn;
		if(sum == 1e9) break;
	}
	if(sum == 1e9) puts("-1");
	else printf("%d", sum);
	return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:47:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N, W, H; scanf("%d%d%d",&N,&W,&H);
               ~~~~~^~~~~~~~~~~~~~~~~~~
robots.cpp:51:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c", &A[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 6144 KB Output is correct
2 Correct 6 ms 6144 KB Output is correct
3 Correct 6 ms 6144 KB Output is correct
4 Correct 7 ms 6272 KB Output is correct
5 Correct 6 ms 6400 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 6144 KB Output is correct
2 Correct 6 ms 6144 KB Output is correct
3 Correct 6 ms 6144 KB Output is correct
4 Correct 7 ms 6272 KB Output is correct
5 Correct 6 ms 6400 KB Output is correct
6 Correct 6 ms 6272 KB Output is correct
7 Correct 6 ms 6244 KB Output is correct
8 Correct 6 ms 6272 KB Output is correct
9 Correct 6 ms 6272 KB Output is correct
10 Correct 6 ms 6208 KB Output is correct
11 Correct 295 ms 44876 KB Output is correct
12 Correct 45 ms 38684 KB Output is correct
13 Correct 38 ms 6776 KB Output is correct
14 Correct 740 ms 53456 KB Output is correct
15 Correct 162 ms 41244 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 6144 KB Output is correct
2 Correct 6 ms 6144 KB Output is correct
3 Correct 6 ms 6144 KB Output is correct
4 Correct 7 ms 6272 KB Output is correct
5 Correct 6 ms 6400 KB Output is correct
6 Correct 6 ms 6272 KB Output is correct
7 Correct 6 ms 6244 KB Output is correct
8 Correct 6 ms 6272 KB Output is correct
9 Correct 6 ms 6272 KB Output is correct
10 Correct 6 ms 6208 KB Output is correct
11 Correct 295 ms 44876 KB Output is correct
12 Correct 45 ms 38684 KB Output is correct
13 Correct 38 ms 6776 KB Output is correct
14 Correct 740 ms 53456 KB Output is correct
15 Correct 162 ms 41244 KB Output is correct
16 Correct 142 ms 11272 KB Output is correct
17 Execution timed out 1543 ms 136268 KB Time limit exceeded
18 Halted 0 ms 0 KB -