アルゴ式（beta版）: C++による「動的計画法 (DP):【補充】練習問題集」- Q. 白黒に塗り分ける (3)

アルゴ式（beta版）の「動的計画法 (DP):【補充】練習問題集」からの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の２つで構成される、Web上で完結した学習コンテンツです。

C++による「動的計画法 (DP):【補充】練習問題集」- Q. 白黒に塗り分ける (3)

僕が作成、提出したコードは、以下のとおりです。

Q. 白黒に塗り分ける (3)

algo-method.com

/*
アルゴ式（beta版）: C++による「動的計画法 (DP):【補充】練習問題集」- Q. 白黒に塗り分ける (3)
Q. 白黒に塗り分ける (3)
https://algo-method.com/tasks/1118
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
bool tf(int m, int p, int bit1, int bit2) {
    for(int j = 0; j < m; ++j) {
        if(bit1 & 1<<j) {
			continue;
		}
        int cnt_white = 0;  
        if((p & 1<<j) == 0) {
			cnt_white++;
		}
        if((bit2 & 1<<j) == 0) {
			cnt_white++;
		}
        if(j > 0 && (bit1 & 1<<(j-1)) == 0) {
			cnt_white++;
		}
        if(j < m-1 && (bit1 & 1<<(j+1)) == 0) {
			cnt_white++;
		}
        if(cnt_white > 2) {
			return false;
		}
    }
    for(int j = 0; j < m; ++j) {
        if(p & 1<<j) {
			continue;
		}
        int cnt_white = 0;
        if((bit1 & 1<<j) == 0) {
			cnt_white++;
		}
        if(j > 0 && (p & 1<<(j-1)) == 0) {
			cnt_white++;
		}
        if(j < m-1 && (p & 1<<(j+1)) == 0) {
			cnt_white++;
		}
        if(cnt_white > 2) {
			return false;
		}
    }
    return true;
}
int main(void) {
	ll m, n;
	cin >> m >> n;
	vector<vector<ll>> a(m, vector<ll>(n));
	for (ll i = 0; i < m; i++) {
		for (ll j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}
	const ll inf = 1<<30;
	vector<vector<vector<ll>>> dp(n + 1, vector<vector<ll>>(1<<m, vector<ll>(1<<m, inf)));
	vector<vector<ll>> v(n, vector<ll>(1<<m, 0));
	for (ll i = 0; i < n; i++) {
		for (ll p = 0; p < (1<<m); p++) {
			ll sum = 0;
			for (ll j = 0; j < m; j++) {
				if (p & 1<<j) {
					sum += a[j][i];
				}
			}
			v[i][p] = sum;
		}
	}
	ll num = (1<<m) - 1;
	dp[0][num][num] = 0;
	for (ll i = 0; i < n; i++) {
		for (ll p = 0; p < (1<<m); p++) {
			for (ll b1 = 0; b1 < (1<<m); b1++) {
				for (ll b2 = 0; b2 < (1<<m); b2++) {
					if (tf(m, p, b1, b2)) {
						dp[i + 1][p][b1] = min(dp[i + 1][p][b1], dp[i][b1][b2]+v[i][p]);
					}
				}
			}
		}
	}
	ll ans = inf;
	for (ll p = 0; p < (1<<m); p++) {
		for (ll b1 = 0; b1 < (1<<m); b1++) {
			ans = min(ans, dp[n][p][b1]);
		}
	}
	cout << ans << endl;
	return 0;
}

設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式（beta版）」です。
algo-method.com