CF1701A Grass Field 题解

根据题意，给定一个 \(2\times2\) 的仅包含 \(0\) 和 \(1\) 的二维数组。定义一个操作，每次可以选择一行和一列将其变成 \(0\)，求最小操作次数。

思路：根据枚举可得共有 \(14\) 种矩阵形态，通过观察可得：

当矩阵中 \(1\) 的数量为 \(0\) 时，即只有一种形态，其最小操作次数为 \(0\)。
当矩阵中 \(1\) 的数量为 \(1\) 时，共有四种形态（分别是 \(1\) 分布在四个角），此时最小操作次数为 \(1\)。
当矩阵中 \(1\) 的数量为 \(2\) 时，共有四种形态（分别是在同一行或同一列，在对角线上），其最小操作次数为 \(1\)。
当矩阵中 \(1\) 的数量为 \(3\) 时，共有四种形态（其形状类似于中文笔画中的横折，将其进行旋转），这时最小操作次数为 \(1\)。
当矩阵中 \(1\) 的数量为 \(4\) 时，只有一种形态，其最小操作次数为 \(2\)。

做法一：根据判断形态得出答案，可以通过此题，但做法二更优，此处使用做法二。

做法二：综上所述，可得当 \(1\) 的数量为 \(0\) 时，最小操作数为 \(0\)；当 \(1\) 的数量为 \(1/2/3\) 时，最小操作数为 \(1\)；当 \(1\) 的数量为 \(4\) 时，最小操作数为 \(2\)。即通过计算 \(1\) 的数量来得出答案，可以直接省去数组。

#include<cstdio>

#include<iostream>

using namespace std;

int t;//共有t组数据

int a;

int cnt;//计算1的数量

int main(){

	scanf("%d",&t);

	while(t--){

		cnt=0;

		for(int i=0;i<4;i++){

			scanf("%d",&a);

			cnt+=a;//统计1的数量

		}

		if(cnt==0) puts("0");

		else if(cnt==1||cnt==2||cnt==3) puts("1");

		else puts("2");

	}

	return 0;

}

巴特西

CF1701A Grass Field 题解

最新文章

热门文章