oj.uz

답안 #375030

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
375030 2021-03-08T21:52:24 Z rainboy 로봇 (APIO13_robots) C
100 / 100
 669 ms 63712 KB 
#include <ctype.h>
#include <stdio.h>
#include <string.h>

#define N	500
#define M	500
#define K	9
#define N_	(N * M * K * K)
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }

int di[] = { -1, 0, 1, 0 };
int dj[] = { 0, 1, 0, -1 };

char cc[N][M + 1]; int dp[N][M][K], n, m;

int solve(int i, int j, int h) {
	if (dp[i][j][h] == -1) {
		int h_, i_, j_;

		dp[i][j][h] = -2;
		if (cc[i][j] == 'C')
			h_ = (h + 1) % 4;
		else if (cc[i][j] == 'A')
			h_ = (h + 3) % 4;
		else
			h_ = h;
		i_ = i + di[h_], j_ = j + dj[h_];
		if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m && cc[i_][j_] != 'x')
			dp[i][j][h] = solve(i_, j_, h_);
		else
			dp[i][j][h] = i * m + j;
	}
	return dp[i][j][h];
}

void sort(int *aa, int *ii, int n, int a_) {
	static int jj[N * M], kk[N * M * K + 2];
	int i, a;

	memset(kk, 0, (a_ + 2) * sizeof *kk);
	for (i = 0; i < n; i++)
		kk[aa[ii[i]] + 1]++;
	for (a = 1; a <= a_ + 1; a++)
		kk[a] += kk[a - 1];
	for (i = 0; i < n; i++)
		jj[kk[aa[ii[i]]]++] = ii[i];
	memcpy(ii, jj, n * sizeof *jj);
}

int main() {
	static int dd[K][K][N * M], qu1[N * M], qu2[N * M];
	int k, h, i, j, l, r, a, head1, cnt1, head2, cnt2, ans;

	scanf("%d%d%d", &k, &m, &n);
	for (i = 0; i < n; i++)
		scanf("%s", cc[i]);
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			for (h = 0; h < 4; h++)
				dp[i][j][h] = -1;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			for (h = 0; h < 4; h++)
				dp[i][j][h] = cc[i][j] == 'x' ? -2 : solve(i, j, h);
	for (l = k - 1; l >= 0; l--)
		for (r = l; r < k; r++) {
			int *dd_ = dd[l][r], ij;

			memset(dd_, 0x3f, n * m * sizeof *dd_);
			head1 = cnt1 = head2 = cnt2 = 0;
			if (l == r) {
				for (i = 0; i < n; i++)
					for (j = 0; j < m; j++)
						if (cc[i][j] == l + '1') {
							ij = i * m + j;
							dd_[ij] = 0, qu1[head1 + cnt1++] = ij;
							break;
						}
			} else
				for (i = 0; i < n; i++)
					for (j = 0; j < m; j++) {
						ij = i * m + j;
						for (a = l; a < r; a++)
							dd_[ij] = min(dd_[ij], dd[l][a][ij] + dd[a + 1][r][ij]);
						if (dd_[ij] != INF)
							qu1[head1 + cnt1++] = ij;
					}
			sort(dd_, qu1, cnt1, n * m * k);
			while (cnt1 || cnt2) {
				int d;

				ij = !cnt2 || cnt1 && dd_[qu1[head1]] < dd_[qu2[head2]] ? qu1[cnt1--, head1++] : qu2[cnt2--, head2++], i = ij / m, j = ij % m, d = dd_[ij] + 1;
				for (h = 0; h < 4; h++) {
					int ij_ = dp[i][j][h];

					if (ij_ != -2 && dd_[ij_] > d)
						dd_[ij_] = d, qu2[head2 + cnt2++] = ij_;
				}
			}
		}
	ans = INF;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			ans = min(ans, dd[0][k - 1][i * m + j]);
	if (ans == INF)
		ans = -1;
	printf("%d\n", ans);
	return 0;
}

Compilation message

robots.c: In function 'main':
robots.c:94:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   94 |     ij = !cnt2 || cnt1 && dd_[qu1[head1]] < dd_[qu2[head2]] ? qu1[cnt1--, head1++] : qu2[cnt2--, head2++], i = ij / m, j = ij % m, d = dd_[ij] + 1;
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
robots.c:56:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   56 |  scanf("%d%d%d", &k, &m, &n);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
robots.c:58:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   58 |   scanf("%s", cc[i]);
      |   ^~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 167 ms 24044 KB Output is correct
12 Correct 7 ms 5612 KB Output is correct
13 Correct 72 ms 17388 KB Output is correct
14 Correct 237 ms 24300 KB Output is correct
15 Correct 148 ms 24044 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 167 ms 24044 KB Output is correct
12 Correct 7 ms 5612 KB Output is correct
13 Correct 72 ms 17388 KB Output is correct
14 Correct 237 ms 24300 KB Output is correct
15 Correct 148 ms 24044 KB Output is correct
16 Correct 417 ms 62576 KB Output is correct
17 Correct 669 ms 63712 KB Output is correct
18 Correct 425 ms 62972 KB Output is correct
19 Correct 407 ms 62652 KB Output is correct
20 Correct 523 ms 63212 KB Output is correct