题目大意

给定一个$2*m$仅由字符$W$和$B$的矩阵，求是否有路径可以经过所有$B$而不经过任何$W$。

---

思路

虽然很多人讲的都是数组dp，但是这个东西实际上会有些抽象和复杂。
其实不如直接模拟这个过程。用一个flag来存储当前位置在上方还是下方。
如下：

以下所有cb均表示'B'，cw均表示'W'。
a，b均为string，表示矩阵的两行，且处理以后从下标1开始。
i初始化为1。

1

如果开头有多个上下两个B则不是很好处理。
注意到开头连续的上下两个B并不会影响到后续的位置在上方或下方，所以可以直接过滤掉：

while(a[i]==cb && b[i]==cb)i++;

2

首先确保当前停下来的列不是两个W:

if(a[i]==cw && b[i]==cw){
    cout << "NO\n";
    return;
}

然后如果当前已经到达了m+1（即整个矩阵都是B）那么可以直接输出答案后返回。

if(i==m+1){
    cout << "YES\n";
    return;
}

3

此时只剩当前列一个W一个B的情况了，需要根据具体情况确定flag初始值。

if(a[i]==cb)flag=0;
else flag=1;

注意完成后要i++来到真正的处理位置。

4

for(;i <= m;i++)开始遍历。
首先，如果当前位置是'W'，则代表没有办法继续往下走了。

if(flag && b[i]==cw){
    cout << "NO\n";
    return;
}
if(!flag && a[i]==cw){
    cout << "NO\n";
    return;
}

然后，如果当前列两个位置都是B，则为了都遍历到需要换一行。

if(a[i]==cb && b[i]==cb){
    flag++;
    flag%=2;
}

5

如果最后没有输出NO，则证明已经到达了，有一条正确路径，直接cout << "YES\n";即可。

---

代码

#include<bits/stdc++.h>
using namespace std;
int t;
#define cw 'W'
#define cb 'B'
void solve(){
    int m;cin >> m;
    string a,b;
    cin >> a >> b;
    a='0'+a;
    b='0'+b;
    int flag=0;//0在上，1在下
    int i = 1;
    while(a[i]==cb && b[i]==cb)i++;
    if(a[i]==cw && b[i]==cw){
        cout << "NO\n";
        return;
    }
    if(i==m+1){
        cout << "YES\n";
        return;
    }
    if(a[i]==cb)flag=0;
    else flag=1;
    i++;
    for(;i <= m;i++){
        if(flag && b[i]==cw){
            cout << "NO\n";
            return;
        }
        if(!flag && a[i]==cw){
            cout << "NO\n";
            return;
        }
        if(a[i]==cb && b[i]==cb){
            flag++;
            flag%=2;
        }
    }
    cout << "YES\n";
}
int main(){
    cin >> t;
    while(t--)solve();
}