We assume \(W\leq H\), because transposing rows and columns does not change the answer.

Let us take a DP (Dynamic Programming) approach where the numbers are decided from the top-left to bottom-right cells in this order: \((1,1)\to(1,2)\to\dots\to(1,W)\to(2,1)\to(2,2)\to\dots\to(2,H)\to\dots\to(H,1)\to(H,2)\to\dots\to(H,W)\).

Assume that we are going to decide the number for the green cell in the figure above. Here, the information of the upper gray cells is irrelevant to the remaining numbers to write. The numbers to write on the current and following cells are solely dependent on those on the blue cells. Thus, it seems possible to do DP with the key being “the numbers written on the last \(W\) cells.”

How many states are there? There are as many as \(3^W\) ways to write numbers on the last \(W\) cells, but among them there are only \(9\times 2^{W-2}\) ways that satisfy the condition that “adjacent cells have different numbers.” Thus, the number of states can be reduced by maintaining only those satisfying the condition.

The complexity is \(O(2^{\min(H,W)}HW)\) or \(O(2^{\min(H,W)}HW\min(H,W))\); since \(\min(H,W)\leq 14\), it is small enough.

Similar problems

• JOI 旗 (JOI Flag)
• Avoid War

from collections import defaultdict

H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
if W > H:
    S = [[S[i][j] for i in range(H)] for j in range(W)]
    H, W = W, H

mod = 998244353

# 前 W マスの状態を W 桁の 10 進法として持つ
# Maintain the states of the last W cells as a decimal integer with W digits
dp = defaultdict(int)
dp[0] = 1
B = 10 ** (W - 1)
for x in range(H):
    for y in range(W):
        ndp = defaultdict(int)
        for pre, val in dp.items():
            for i in range(1, 4):
                if S[x][y] == str(i) or S[x][y] == "?":
                    top = pre // B
                    if top == i:  # If it is equal to the cell above
                        continue
                    if y > 0:
                        back = pre % 10
                        if back == i:  # If it is equal to the cell to the left
                            continue
                    num = (pre * 10 + i) % (10 * B)
                    ndp[num] += val
                    ndp[num] %= mod
        dp = ndp

ans = sum(dp.values()) % mod
print(ans)