Hamiltonian Wall

# Hamiltonian Wall

## 题面翻译

给你一个 $2\times m$ 的矩阵，矩阵中只可能包含字符 `B` 和 `W`。每一列都有字符 `B`。问能否找出一条路径，满足：

- 路径中相邻两格有公共边（只有公共点的不算）。
- 每个 `B` 格恰好被覆盖一次。
- 每个 `W` 格都没有被覆盖到。

如果存在这样的路径，输出 `YES`，否则输出 `NO`。

## 题目描述

Sir Monocarp Hamilton is planning to paint his wall. The wall can be represented as a grid, consisting of $ 2 $ rows and $ m $ columns. Initially, the wall is completely white.

Monocarp wants to paint a black picture on the wall. In particular, he wants cell $ (i, j) $ (the $ j $ -th cell in the $ i $ -th row) to be colored black, if $ c_{i, j} = $ 'B', and to be left white, if $ c_{i, j} = $ 'W'. Additionally, he wants each column to have at least one black cell, so, for each $ j $ , the following constraint is satisfied: $ c_{1, j} $ , $ c_{2, j} $ or both of them will be equal to 'B'.

In order for the picture to turn out smooth, Monocarp wants to place down a paint brush in some cell $ (x_1, y_1) $ and move it along the path $ (x_1, y_1), (x_2, y_2), \dots, (x_k, y_k) $ so that:

- for each $ i $ , $ (x_i, y_i) $ and $ (x_{i+1}, y_{i+1}) $ share a common side;
- all black cells appear in the path exactly once;
- white cells don't appear in the path.

Determine if Monocarp can paint the wall.

## 输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of testcases.

The first line of each testcase contains a single integer $ m $ ( $ 1 \le m \le 2 \cdot 10^5 $ ) — the number of columns in the wall.

The $ i $ -th of the next two lines contains a string $ c_i $ , consisting of $ m $ characters, where each character is either 'B' or 'W'. $ c_{i, j} $ is 'B', if the cell $ (i, j) $ should be colored black, and 'W', if the cell $ (i, j) $ should be left white.

Additionally, for each $ j $ , the following constraint is satisfied: $ c_{1, j} $ , $ c_{2, j} $ or both of them are equal to 'B'.

The sum of $ m $ over all testcases doesn't exceed $ 2 \cdot 10^5 $ .

## 输出格式

For each testcase, print "YES" if Monocarp can paint a wall. Otherwise, print "NO".

## 样例 #1

### 样例输入 #1

```
6
3
WBB
BBW
1
B
B
5
BWBWB
BBBBB
2
BW
WB
5
BBBBW
BWBBB
6
BWBBWB
BBBBBB
```

### 样例输出 #1

```
YES
YES
NO
NO
NO
YES
```

## 提示

In the first testcase, Monocarp can follow a path $ (2, 1) $ , $ (2, 2) $ , $ (1, 2) $ , $ (1, 3) $ with his brush. All black cells appear in the path exactly once, no white cells appear in the path.

In the second testcase, Monocarp can follow a path $ (1, 1) $ , $ (2, 1) $ .

In the third testcase:

- the path $ (1, 1) $ , $ (2, 1) $ , $ (2, 2) $ , $ (2, 3) $ , $ (1, 3) $ , $ (2, 4) $ , $ (2, 5) $ , $ (1, 5) $ doesn't suffice because a pair of cells $ (1, 3) $ and $ (2, 4) $ doesn't share a common side;
- the path $ (1, 1) $ , $ (2, 1) $ , $ (2, 2) $ , $ (2, 3) $ , $ (1, 3) $ , $ (2, 3) $ , $ (2, 4) $ , $ (2, 5) $ , $ (1, 5) $ doesn't suffice because cell $ (2, 3) $ is visited twice;
- the path $ (1, 1) $ , $ (2, 1) $ , $ (2, 2) $ , $ (2, 3) $ , $ (2, 4) $ , $ (2, 5) $ , $ (1, 5) $ doesn't suffice because a black cell $ (1, 3) $ doesn't appear in the path;
- the path $ (1, 1) $ , $ (2, 1) $ , $ (2, 2) $ , $ (2, 3) $ , $ (2, 4) $ , $ (2, 5) $ , $ (1, 5) $ , $ (1, 4) $ , $ (1, 3) $ doesn't suffice because a white cell $ (1, 4) $ appears in the path.

//Hamiltonian Wall
//一开始想的dfs,从最左边开始,然后一直遍历,如果全部能遍历一次的话,就可以
//但是一直超时,后来高人点明由于就两行,可以用模拟暴力来求
//如果同列可以走,先走同列,然后再走同行,如果不能走同行就直接返回
#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+3,mod=1e9+7;
string s[2];
int n,t,res,num,ans,m;
int dx[]={1,-1,0},dy[]={0,0,1};
bool vis[2][N];
bool dfs(int u,int v,int cnt)
{
    if(cnt==num) return true;
    for(int i=0;i<3;i++){
        int x=u+dx[i],y=v+dy[i];
        if(x>=0&&x<=1&&y>=0&&y<n&&!vis[x][y]&&s[x][y]=='B'){
            vis[x][y]=true;
            if(dfs(x,y,cnt+1)) return true;
            vis[x][y]=false;
        }
    }
    return false;
}
int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        num=0;
        bool f=false,f1=false,f2=false;
        cin>>s[0]>>s[1];
        for(int i=0;i<n;++i){
            if(s[0][i]=='B') num++;
            if(s[1][i]=='B') num++;
        }
            if(f) break;
            if(s[0][0]=='B'){
                vis[0][0]=true;
                if(dfs(0,0,1)) cout<<"YES"<<endl,f1=true;
                for(int i=0;i<n;i++) vis[0][i]=false,vis[1][i]=false;
                f=true;
            }
            if(s[1][0]=='B'&&!f1){
                vis[1][0]=true;
                if(dfs(1,0,1)) cout<<"YES"<<endl,f2=true;
                f=true;
            } 
        if(!f1&&!f2) cout<<"NO"<<endl;
        for(int i=0;i<n;i++) vis[0][i]=false,vis[1][i]=false;
    }
    return 0;
}

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
string s[2];
int n,t,a[N],f[N],res,num,ans,m;
bool vis[N];
bool chk(int u)
{
    bool now=u;
    if(s[u][0]=='B') now=!now;
    for(int i=1;i<n;i++){
        if(s[now][i]=='W') return false;
        if(s[!now][i]=='B') now=!now;
    } 
    return true;
}
bool solve()
{
    cin >> n >> s[0] >> s[1];
    if (s[0][0] == 'B') {if (chk(1)) return true;}
    if (s[1][0] == 'B') {if (chk(0)) return true;}
    return false;
}
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        if(solve()) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}