Submission #60013646

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD_BY 998244353
int add(int a, int b) {
  return a + b - MOD_BY * (a + b >= MOD_BY);
}
struct node_s {
  int value;
  struct node_s *next[2];
};
int* getValuePtr(struct node_s** node, int key) {
  if (*node == NULL) {
    *node = malloc(sizeof(**node));
    if (*node == NULL) exit(2);
    (*node)->value = -1;
    (*node)->next[0] = NULL;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

#define MOD_BY 998244353

int add(int a, int b) {
	return a + b - MOD_BY * (a + b >= MOD_BY);
}

struct node_s {
	int value;
	struct node_s *next[2];
};

int* getValuePtr(struct node_s** node, int key) {
	if (*node == NULL) {
		*node = malloc(sizeof(**node));
		if (*node == NULL) exit(2);
		(*node)->value = -1;
		(*node)->next[0] = NULL;
		(*node)->next[1] = NULL;
	}
	if (key == 0) {
		return &(*node)->value;
	} else {
		return getValuePtr(&(*node)->next[key & 1], key >> 1);
	}
}

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

int keyModBy;
char grid[256][256];
struct node_s* memo[256][16];

int calc(int y, int x, int key) {
	if (y >= H) {
		return 1;
	} else {
		int* memoPtr = getValuePtr(&memo[y][x], key);
		int i, newKeyBase = key * 3 % keyModBy;
		char orig = grid[y][x];
		int ans = 0;
		if (*memoPtr >= 0) return *memoPtr;
		for (i = 0; i < 3; i++) {
			grid[y][x] = '1' + i;
			if (
				(orig == '?' || grid[y][x] == orig) &&
				(y == 0 || grid[y][x] != grid[y - 1][x]) &&
				(x == 0 || grid[y][x] != grid[y][x - 1])
			) {
				ans = add(ans, calc(y + (x == W - 1), (x + 1) % W, newKeyBase + i));
			}
		}
		grid[y][x] = orig;
		return *memoPtr = ans;
	}
}

int main(void) {
	int i, j;
	if (scanf("%d%d", &H, &W) != 2) return 1;
	for (i = 0; i < H; i++) {
		if (scanf("%255s", S[i]) != 1) return 1;
	}
	if (H < W) {
		for (i = 0; i < H; i++) {
			for (j = 0; j < W; j++) {
				grid[j][i] = S[i][j];
			}
		}
		i = H;
		H = W;
		W = i;
	} else {
		memcpy(grid, S, sizeof(S));
	}
	for (keyModBy = 1, i = 0; i < W; i++) keyModBy *= 3;
	printf("%d\n", calc(0, 0, 0));
	return 0;
}

/*

H×W <= 200 → HとWのどっちかは14以下
適宜転置し、大きくない方をWにする

上から下、左から右に順番に埋める
埋める場所の前W個を状態としてメモ
隣接するマスが異なる数字という制約があるので、最初と行が変わる所だけ制約が外れ、
(3**2)*(2**(W-2)) = 36864 通り

36864 * 200 = 7,372,800 これは十分小さい

3通りをそのままやると 3**14 = 4782969 通り
4782969 * 200 = 956,593,800 これはちょっと厳しいか

*/

Submission Info

Judge Result