需要注意到两个约束条件:
1. 给出的图最多只有一个连通区域
2. 网格只有两行
所以把一个连通区域分成三个连通块的方法只能出现在这样两个情况中:
①
x、x
、、、
②
、、、
x、X
所以需要统计这种图形出现的次数,即满足分割连通区域的点数
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include "bits/stdc++.h"
using namespace std;
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fios ofstream("test.txt");cout.rdbuf(out.rdbuf())
#define INF 0xf3f3f3f3f
#define MINF 2147483647
#define eps 1e-6
#define PI acos(-1)
#define lowbit(x) (x & (-x))
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 200010;
int n;
char g[2][N];
bool check_1(int x)
{
if(g[0][x - 1] != 'x') return false;
if(g[1][x - 1] != '.') return false;
if(g[0][x] != '.') return false;
if(g[1][x] != '.') return false;
if(g[0][x + 1] != 'x') return false;
if(g[1][x + 1] != '.') return false;
return true;
}
bool check_2(int x)
{
if(g[0][x - 1] != '.') return false;
if(g[1][x - 1] != 'x') return false;
if(g[0][x] != '.') return false;
if(g[1][x] != '.') return false;
if(g[0][x + 1] != '.') return false;
if(g[1][x + 1] != 'x') return false;
return true;
}
int main()
{
int T;
cin >> T;
while(T--)
{
cin >> n;
for(int i = 0; i < 2; i++)
for(int j = 0; j < n; j++)
cin >> g[i][j];
int res = 0;
for(int i = 1; i < n - 1; i++)
if(check_1(i) || check_2(i)) res++;
cout << res << endl;
}
return 0;
}