AtCoder ABC #379 (トヨタ自動車プログラミングコンテスト2024#11) : G - Count Grid 3-coloring

バグが取り切れず時間内に終わらなかった。
https://atcoder.jp/contests/abc379/tasks/abc379_g

問題

H*Wのグリッドがあり、一部のマスには1～3の数字が入っている。
全マスに1～3のいずれかの数字を入れるとき、隣接マスに同じ数字が入らないような入れ方は何通りか。

解法

H＜Wなら先に90度回転するなどしてW≦Hにしておく。

row-major order順で値を埋めて行くが、その際各列確定済みの最下段の数値を状態として持とう。
一見3^W通り状態がありそうだが、隣接マスには同じ数字が入らないので高々3^2*2^(W-2)通りの状態で済む。
あとは、各マス、上と左の値を見ながら同じ数字が隣接しないように埋めて行く。

int H,W;
string V[200];
string S[200];

const ll mo=998244353;
ll p10[18];

vector<int> decode(int first,int mask) {
	int i;
	vector<int> V={first};
	FOR(i,W-1) V.push_back((V.back()+1+(mask>>i)%2)%3);
	return V;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) cin>>V[y];
	
	if(W>H) {
		FOR(y,H) FOR(x,W) S[x].push_back(V[y][x]);
		swap(W,H);
	}
	else {
		FOR(y,H) S[y]=V[y];
	}
	
	p10[0]=1;
	FOR(i,16) p10[i+1]=p10[i]*10;
	
	map<ll,ll> F,T;
	F[0]=1;
	FOR(y,H) {
		FOR(x,W) {
			T.clear();
			FORR2(a,b,F) {
				ll p=a/p10[W-1-x]%10;
				ll q=a/p10[W-x]%10;
				for(j=1;j<=3;j++) {
					if(S[y][x]!='?'&&S[y][x]!='0'+j) continue;
					if(j==p||j==q) continue;
					ll na=a+(j-p)*p10[W-1-x];
					(T[na]+=b)%=mo;
				}
			}
			swap(F,T);
		}
	}
	
	ll ret=0;
	FORR2(a,b,F) ret+=b;
	cout<<ret%mo<<endl;
	
}

まとめ

雑に10進法で状態を持っても間に合ったのか…。
うまく状態をシリアルな数値にencodeしようとしてバグを作りこんでしまった。