二部グラフの最大マッチングで解きます。公式のTutorialにも記載があるし、面白味はないです。
題意
- チェスのポーンがあり、黒(1列目にある)、白(2列目にあるとしてよい)の順に0=駒がない,1駒があるで与えられる
- 黒は動かない。白は何もない駒に対してまっすぐ進むことができる。黒がまっすぐある場合進めない。白は１つ斜めにある駒はとれる。
- さて、最大で何個の駒が1列目に行けるか？なお、白は１列目に行っても消滅しない
こう考えた
最大流で解きます。
- sから白(下)にはすべて辺を張ります(1にだけ張っても良いです) cap=1です。
- 黒(上)からtにはすべて辺を張ります。cap=1です。これは駒がある場合(1)もない場合(0)も白が到達する可能性があるのですべて辺を張らないといけません。
- 白から黒に辺を張ります。白のインデックスを$i$とすると、
- 黒_$i$が0の時、辺をcap=1で張ります。何もないマスにはまっすぐ進めます
- 黒i-1、あるいは、黒i+1が1の場合、それぞれ独立にcap=1で辺を張ります。白_$i$からcap=1で張ります。これは斜めの駒をとれることを意味します
以上の辺を張って最大流を流すと、このグラフにおける、tに到達できる最大のフロー = 1列目に到達できる最大の白のコマ数が求められます。
実装
$\pm 1$の処理が面倒なので、sを読み込む際に左右に$0$を付けて読み込みます。今回の制約ではこれは結果に影響しません。その際、$n$は$+2$して考える必要があることに注意です。
/* ACLをぺたり */
void solve() {
int n; cin >> n;
string s;
vector<int> dat1(n+2);
vector<int> dat2(n+2);
cin >> s; REP(i, n) dat1.at(i+1) = s[i] - 0x30;
cin >> s; REP(i, n) dat2.at(i+1) = s[i] - 0x30;
mf_graph<int> mf((n + 2) * 2 + 2);
int ss, tt;
int node = n + 2;
ss = node*2;
tt = node*2 + 1;
FOR(i, 1, n+1){
mf.add_edge(ss, i, 1);
mf.add_edge(node+i, tt, 1);
if(dat2.at(i) == 0) continue;
if(dat1.at(i) == 0) mf.add_edge(i, node + i, 1);
if(dat1.at(i-1) == 1) mf.add_edge(i, node + i-1, 1);
if(dat1.at(i+1) == 1) mf.add_edge(i, node + i +1, 1);
}
cout << mf.flow(ss, tt) << "\n";
return;
// debug
vector<mf_graph<int>::edge> edges = mf.edges();
for (auto &e : edges) {
//cout << e.from <<","<<e.to << "," << e.flow << e.cap<< endl;
}
}
int main(int argc, char *argv[]) {
int q; cin >> q;
REP(qq, q) solve();
}