题目描述

小猫有一个 2\times N2×N 的棋盘，每一个格子放着一个黑棋子或白棋子。

小熊觉得小猫的棋盘不够好看，想要把棋盘上的一部分白棋子替换成黑棋子，使得所有黑棋子都能够在仅允许上下左右四个方向走，且仅经过黑棋子在的格子的情况下两两互相到达。

小熊想知道至少要将多少个白棋子替换成黑棋子。

注意：不能将黑棋子替换成白棋子。

输入描述

第一行有一个正整数 NN (1 \le N \le 10^51≤N≤105)。

接下来两行，每行 NN 个整数，描述整个棋盘。若第 ii 行的第 jj 个整数是 00，代表棋盘 (i,j)(i,j) 的位置放着白棋子，若是 11 则放着黑棋子。

数据保证至少存在一个黑棋子。

输出描述

输出一行包含一个整数，表示答案。

样例输入 1

3
1 0 0
0 0 1

样例输出 1

2

样例输入 2

5
0 1 0 1 0
0 0 1 0 0

样例输出 2

1

提示

样例一中可以将第一行的两个白棋子替换成黑棋子。

样例二中可以将位置 (1, 3)(1,3) 的白棋子换成黑棋子。

思路：

由于题目说这个矩阵只有两行，我们知道，对于每一列，2块方格，有4个组合方式，

有1的列，只有以下三个方式是可能需要变化前面的白棋子的。

分别是：

两个1

上0下1

上1下0

如果是两个1，我们可以从上一个有1的位置，直线连接过来到当前的一个1，记上一个1出来的位置是last

则对答案的贡献是 i-last-1

如果上1下0，我们需要根据last位置的1是什么情况，。如果上行有1，那么贡献是  i-last-1 否则是 i-last

上0下1 和上面一样来处理即可。

每遇到一列有1就去维护 last 和 1在上还是在下的信息Pos

细节见代码：

#include
#include
#include
#include
#include
#include
#include
#include

//freopen("D:\\\\common\_text\\\\code\_stream\\\\in.txt","r",stdin);  
//freopen("D:\\\\common\_text\\\\code\_stream\\\\out.txt","w",stdout);  
gbtb;  
cin>>n;  
int r=-;  
int l=inf;  
repd(j,,)  
repd(i,,n)  
{  
    cin>>a\[i\]\[j\];  
    if(a\[i\]\[j\])  
    {  
        r=max(r,i);  
        l=min(l,i);  
    }  
}  
int last=l;  
int pos;  
if(a\[l\]\[\]==a\[l\]\[\])  
{  
    pos=;  
}else if(a\[l\]\[\])  
{  
    pos=;  
}else  
{  
    pos=;  
}  
int ans=;  
// cout<<l<<" "<<r<<endl;  
repd(i,l+,r)  
{  
    if(a\[i\]\[\]||a\[i\]\[\])  
    {  
        if(a\[i\]\[\]==a\[i\]\[\])  
        {  
            pos=;  
            ans+=i-last-;  
        }else if(a\[i\]\[\])  
        {  
            if(pos==)  
            {  
                pos=;  
                ans+=i-last-;  
            }else if(pos==)  
            {  
                pos=;  
                ans+=i-last;  
            }else  
            {  
                pos=;  
                ans+=i-last-;  
            }  
        }else if(a\[i\]\[\])  
        {  

// db(pos);
if(pos==)
{
pos=;
ans+=i-last-;
}else if(pos==)
{
// db(last);
ans+=i-last;
pos=;
}else
{
pos=;
ans+=i-last-;
}
}
last=i;
}
}
cout<<ans<<endl;
return ;
}

inline void getInt(int* p) {
char ch;
do {
ch = getchar();
} while (ch == ' ' || ch == '\n');
if (ch == '-') {
*p = -(getchar() - '');
while ((ch = getchar()) >= '' && ch <= '') { *p = *p * - ch + ''; } } else { *p = ch - ''; while ((ch = getchar()) >= '' && ch <= '') {
*p = *p * + ch - '';
}
}
}