Comet OJ - Contest #3——棋盘

题目链接
题目描述

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

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

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

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

输入描述

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

接下来两行，每行 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
解题思思路：
首先题目给的是两行的棋盘，使得所有黑棋都能连在一起的最少放黑棋的方案，输出的是放黑棋的个数；
那么我们可以想一想，可能出现的情况，

#include<bits/stdc++.h>
using namespace std;
int a[100005][2];
int main()
{
   
	int n,zhi=-1,ans=0,k=0,maxv=-1;
	cin>>n;
	for(int i=0;i<n;i++)
	{
   
		cin>>a[i][0];
		if(i>maxv&&a[i][0]==1)
            maxv=i;
	}
	for(int i=0;i<n;i++)
	{
   
		cin>>a[i][1];
		if(i>maxv&&a[i][1]==1)	maxv=i;
	}
	for(int i=0;i<n;i++)
	{
   
		if(a[i][0]==1&&a[i][1]==1)
		{
   
			zhi=3;k=i+1;
			break;
		}
		if(a[i][0]==1)
		{
   
			zhi=0;k=i+1;
			break;
		}
		if(a[i][1]==1)
		{
   
			zhi=1;k=i+1;
			break;
		}
	}
	for(int i=k;i<=maxv;i++)
	{
   
		if(a[i][0]==1&&a[i][1]==1)
		{
   
			zhi=3;
			continue;
		}
		if(a[i][0]==1)
		{
   
			if(zhi!=0)
			{
   
				if(zhi==3)
				{
   
					zhi=0;
					continue;
				}
				zhi=3;
				ans++;
			}
			continue;
		}
		if(a[i][1]==1)
		{
   
			if(zhi!=1)
			{
   
				if(zhi==3)
				{
   
					zhi=1;
					continue;
				}
				zhi=3;
				ans++;
			}
			continue;
		}
		ans++;
	}
	cout<<ans;
	return 0;
}