题解详见https://www.luogu.com.cn/article/73itpj0d
总共分为三种情况,需要注意的是,从存在#的第一列开始,那么操作之后的每一列都会有#,所以就避免考虑下面的情况:
.# .. .#
.# .# ..
因为我们一步一步通过循环来实现第 i 列和第 i+1 列的连通性!
注意边界问题for(int i = l; i < r; i ++)
,不要取等号。
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string s1,s2;
int l,r;
void Print()
{
for(int i = l; i <= r; i ++)
cout << s1[i];
cout << endl;
for(int i = l; i <= r; i ++)
cout << s2[i];
cout << endl;
}
int main()
{
cin >> s1 >> s2;
int n = s1.size();
//首先寻找需要连通#的左右边界
l = n+1, r = -1;
for(int i = 0; i < n; i ++)
{
if(s1[i] == '#' || s2[i] == '#')
{
l = min(l,i);
r = max(r,i);
}
}
// printf("%d %d\n",l,r);
int cnt = 0;
for(int i = l; i < r; i ++) //循环的目的是检查并确保第 i 列和第 i+1 列之间的连通性
{
//Case1
if(s1[i]=='#' && s1[i+1]=='.' && s2[i]=='.')
{
s1[i+1] = '#';
cnt ++;
// Print();
}
//Case2
else if(s1[i]=='.' && s2[i]=='#' && s2[i+1]=='.')
{
s2[i+1] = '#';
cnt ++;
// Print();
}
//Case3
else if(s1[i]=='#' && s1[i+1]=='.' && s2[i]=='#' && s2[i+1]=='.')
{//这种情况被俩.挡住,必须得选择一个填上#
int nex1 = r+1, nex2 = r+1;
for(int j = i+2; j <= r; j ++) //寻找下一次最先出现#的位置,选择近者填#连通
{
if(s1[j] == '#')
{
nex1 = j;
break;
}
else if(s2[j] == '#')
{
nex2 = j;
break;
}
}
// printf("-%d %d-\n",nex1,nex2);
if(nex1 <= nex2) //nex1较近
{
s1[i+1] = '#';
cnt ++;
}
else
{
s2[i+1] = '#';
cnt ++;
}
// Print();
}
}
cout << cnt;
return 0;
}