Submission #144890


Source Code Expand

Copy
#include <stdio.h>
#include <string.h>

#define QUEUE_SIZE 10000
#define INF 100000000
#define min(a, b) (((a) < (b)) ? (a) : (b))
#define next(i) (((i) + 1) % QUEUE_SIZE)

char fieldT[52][53], fieldTmp[52][53];
const int di[4] = {-1, 0, 1, 0}, dj[4] = {0, -1, 0, 1};
int fieldD[52][52], fieldK[52][52], fieldP[52][52], r, c;
int queue[QUEUE_SIZE], front, rear;

void init() {
	front = 0;
	rear = 0;
}

void enqueue(int x) {
	queue[rear] = x;
	rear = next(rear);
}

int dequeue(void) {
	int t = queue[front];
	front = next(front);
	return t;
}

int bfs(int si, int sj, int gi, int gj, int sk, int mode) {
	int l, m;

	for (l = 1; l < r + 1; l++)
		for (m = 1; m < c + 1; m++) {
			fieldD[l][m] = INF;
			fieldK[l][m] = -INF;
		}

	init();

	fieldD[si][sj] = 0;
	enqueue(si * 1000000 + sj * 1000 + sk);
	while (front != rear) {
		int tmp = dequeue();
		int i = tmp / 1000000, j = tmp / 1000 % 1000, k = tmp % 1000;

		for (l = 0; l < 4; l++) {
			int ni = i + di[l], nj = j + dj[l];

			if (fieldD[ni][nj] == INF || fieldK[ni][nj] < k) {
				switch (fieldT[ni][nj]) {
				case '.': case 'S':
					fieldP[ni][nj] = i * 1000 + j;
					fieldD[ni][nj] = fieldD[i][j] + 1;
					fieldK[ni][nj] = k;
					enqueue(ni * 1000000 + nj * 1000 + k);
					break;
				case 'E':
					if (k) {
						fieldP[ni][nj] = i * 1000 + j;
						fieldD[ni][nj] = fieldD[i][j] + 1;
						fieldK[ni][nj] = k - 1;
						enqueue(ni * 1000000 + nj * 1000 + k - 1);
					}
					break;
				case 'C':
					fieldP[ni][nj] = i * 1000 + j;
					if (mode == 0)
						return fieldD[i][j] + 1;
					else {
						fieldD[ni][nj] = fieldD[i][j] + 1;
						fieldK[ni][nj] = k;
						enqueue(ni * 1000000 + nj * 1000 + k);
					}
					break;
				case 'G':
					fieldP[ni][nj] = i * 1000 + j;
					if (mode == 1)
						return fieldD[i][j] + 1;
					else {
						fieldD[ni][nj] = fieldD[i][j] + 1;
						fieldK[ni][nj] = k;
						enqueue(ni * 1000000 + nj * 1000 + k);
					}
					break;
				}
			}
		}
	}

	return 0;
}

void del(int i, int j) {
	if (fieldT[i][j] == 'S')
		return;

	if (fieldT[i][j] == 'E')
		fieldT[i][j] = '.';

	del(fieldP[i][j] / 1000, fieldP[i][j] % 1000);
}

int main(void) {
	int i, j;
	int k, si, sj, ci, cj, gi, gj, min;

	scanf("%d %d %d", &r, &c, &k);
	for (i = 0; i < r; i++)
		scanf("%s", fieldTmp[i + 1] + 1);
	for (i = 0; i < c + 2; i++)
		fieldTmp[0][i] = fieldTmp[r + 1][i] = 'T';
	for (i = 0; i < r; i++)
		fieldTmp[i + 1][0] = fieldTmp[i + 1][c + 1] = 'T';

	for (i = 0; i < r + 2; i++)
		for (j = 0; j < c + 2; j++)
			switch (fieldTmp[i][j]) {
			case 'S':
				si = i;
				sj = j;
				break;
			case 'C':
				ci = i;
				cj = j;
				break;
			case 'G':
				gi = i;
				gj = j;
				break;
			}

	min = INF;
	for (i = 0; i <= k; i++) {
		int d1;

		memcpy(fieldT, fieldTmp, sizeof fieldTmp);

		d1 = bfs(si, sj, ci, cj, i, 0);
		if (d1) {
			int d2;

			del(ci, cj);

			d2 = bfs(ci, cj, gi, gj, k - i, 1);
			if (d2)
				min = min(min, d1 + d2);
		}
	}

	printf("%d\n", min == INF ? -1 : min);

	return 0;
}

Submission Info

Submission Time
Task C - 最後の森
User zeosutt
Language C (GCC 4.6.4)
Score 0
Code Size 3152 Byte
Status
Exec Time 102 ms
Memory 804 KB

Compile Error

./Main.c: In function ‘main’:
./Main.c:108:7: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
./Main.c:110:8: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]

Test Cases

Set Name Score / Max Score Test Cases
All 0 / 100 case_01.txt, case_02.txt, case_03.txt, case_04.txt, case_05.txt, case_06.txt, case_07.txt, case_08.txt, case_09.txt, case_10.txt, case_11.txt, case_12.txt, case_13.txt, case_14.txt, case_15.txt, case_16.txt, case_17.txt, case_18.txt, case_19.txt, case_20.txt, case_21.txt, case_22.txt, case_23.txt, case_24.txt, case_25.txt, case_26.txt, case_27.txt, case_28.txt, case_29.txt, case_30.txt
Case Name Status Exec Time Memory
case_01.txt 19 ms 804 KB
case_02.txt 18 ms 800 KB
case_03.txt 19 ms 800 KB
case_04.txt 19 ms 804 KB
case_05.txt 19 ms 800 KB
case_06.txt 19 ms 800 KB
case_07.txt 19 ms 796 KB
case_08.txt 19 ms 672 KB
case_09.txt 19 ms 800 KB
case_10.txt 20 ms 800 KB
case_11.txt 19 ms 800 KB
case_12.txt 19 ms 800 KB
case_13.txt 21 ms 676 KB
case_14.txt 76 ms 672 KB
case_15.txt 18 ms 792 KB
case_16.txt 24 ms 800 KB
case_17.txt 54 ms 804 KB
case_18.txt 19 ms 796 KB
case_19.txt 35 ms 792 KB
case_20.txt 31 ms 804 KB
case_21.txt 102 ms 672 KB
case_22.txt 20 ms 800 KB
case_23.txt 29 ms 800 KB
case_24.txt 33 ms 796 KB
case_25.txt 69 ms 804 KB
case_26.txt 20 ms 800 KB
case_27.txt 19 ms 796 KB
case_28.txt 22 ms 796 KB
case_29.txt 19 ms 800 KB
case_30.txt 20 ms 796 KB
sample_01.txt 19 ms 796 KB
sample_02.txt 19 ms 800 KB
sample_03.txt 19 ms 684 KB
sample_04.txt 18 ms 796 KB