# 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; }