Submission #69695960

Source Code Expand

#include <stdio.h>

int H, W;
char S[8][8];

int gen;
int memo_gen[7][7][1 << 8];
int memo[7][7][1 << 8];

int calc(int y, int x, int status) {
	int ans;
	if (x >= W) return calc(y + 1, 0, status);
	if (y >= H) return 0;
	if (memo_gen[y][x][status] == gen) return memo[y][x][status];
	/* 白にする */
	ans = calc(y, x + 1, (status << 1) & ((1 << (W + 1)) - 1)) + (S[y][x] == '#');
	/* 黒にする */
	if (
		S[y][x] == '#' && (
			x == 0 ||
			(status & 1) != 1 ||
			(status >> (W - 1)) != 3
		)
	) {
		int candidate = calc(y, x + 1, ((status << 1) | 1) & ((1 << (W + 1)) - 1));
		if (candidate < ans) ans = candidate;
	}
	memo[y][x][status] = ans;
	memo_gen[y][x][status] = gen;
	return ans;
}

int main(void) {
	int T;
	if (scanf("%d", &T) != 1) return 1;
	for (gen = 1; gen <= T; gen++) {
		int i;
		if (scanf("%d%d", &H, &W) != 2) return 1;
		for (i = 0; i < H; i++) {
			if (scanf("%7s", S[i]) != 1) return 1;
		}
		printf("%d\n", calc(0, 0, 0));
	}
	return 0;
}

/*

.......
.######
##?....
.......

? を決める → ? の位置と # の状態 (幅+1 個) でメモ化探索

*/

Submission Info

Submission Time
Task D - 2x2 Erasing 2
User mikecat
Language C (gcc 12.2.0)
Score 425
Code Size 1148 Byte
Status AC
Exec Time 9 ms
Memory 1852 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 425 / 425
Status
AC × 1
AC × 27
Set Name Test Cases
Sample example_00.txt
All example_00.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt
Case Name Status Exec Time Memory
example_00.txt AC 1 ms 1828 KiB
hand_00.txt AC 9 ms 1796 KiB
hand_01.txt AC 0 ms 1728 KiB
hand_02.txt AC 2 ms 1676 KiB
hand_03.txt AC 1 ms 1712 KiB
hand_04.txt AC 9 ms 1720 KiB
hand_05.txt AC 0 ms 1664 KiB
random_00.txt AC 1 ms 1692 KiB
random_01.txt AC 1 ms 1852 KiB
random_02.txt AC 1 ms 1728 KiB
random_03.txt AC 1 ms 1800 KiB
random_04.txt AC 1 ms 1700 KiB
random_05.txt AC 1 ms 1796 KiB
random_06.txt AC 3 ms 1680 KiB
random_07.txt AC 3 ms 1820 KiB
random_08.txt AC 3 ms 1832 KiB
random_09.txt AC 4 ms 1736 KiB
random_10.txt AC 2 ms 1752 KiB
random_11.txt AC 5 ms 1808 KiB
random_12.txt AC 5 ms 1796 KiB
random_13.txt AC 5 ms 1732 KiB
random_14.txt AC 5 ms 1824 KiB
random_15.txt AC 2 ms 1696 KiB
random_16.txt AC 5 ms 1816 KiB
random_17.txt AC 5 ms 1796 KiB
random_18.txt AC 5 ms 1820 KiB
random_19.txt AC 5 ms 1696 KiB