제출 #375030

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
375030		rainboy	로봇 (APIO13_robots)	C11	100 / 100	669 ms	63712 KiB

robots

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40