AcWing 5472. 铺瓷砖(贪心)
原题链接
困难
作者:
逸误
,
2024-04-05 16:26:10
,
所有人可见
,
阅读 6
//为了修正边界条件不要忘记初始化0和n+1列的元素!!!
//贪心:从左边的列往右边扫,如果有一列两个0,就判断,可不可以往左拐,不行再考虑往右拐
//肯定优先往左拐,因为左边的位置不放就浪费了
#include <iostream>
#include <string>
using namespace std;
const int N = 105;
int n;
int g[N][2];
int res;
int main()
{
string str;
for(int i=0;i<2;i++)
{
cin>>str;
n=str.size();
for(int j=1;j<=n;j++)
{
g[j][i]=str[j-1]-'0';
}
}
g[0][0]=1;
g[0][1]=1;//第0列和第n+1列都视为有瓷砖!防止访问越界写的
g[n+1][0]=1;
g[n+1][1]=1;
//第一次写的时候忘记了初始化后面的墙壁!
for(int i=1;i<=n;i++)
{
if(!g[i][0]&&!g[i][1])//两个都是0
{
if(!g[i-1][0]||!g[i-1][1])//左边有空位可以放
{
g[i][0]=1,g[i][1]=1;//左边放了,不管也没事
res++;
}
else if(!g[i+1][0])
{
g[i][0]=1,g[i][1]=1,g[i+1][0]=1;
res++;
}
else if(!g[i+1][1])
{
g[i][0]=1,g[i][1]=1,g[i+1][1]=1;
res++;
}
}
}
cout<<res<<endl;
return 0;
}