CF1701A Grass Field 题解

题意简述

给出一个 $2 \times 2$ 的场地，其中 $1$ 代表草，$0$ 代表空地。

现在可以选择一行和一列的草全部切割成空地（原来是空地就不变）。

求最少要切割几次才能将这块地完全变成空地。

解题思路

分类讨论。

因为 $2 \times 2$ 实在是太小了，我们可以将含草的格子数从 $0 \to 4$ 讨论一遍。

1. $cnt_{grass} = 0$。

$\begin{matrix} 0 & 0\\ 0 & 0\\ \end{matrix}$

已经全部是空地了，不用再切了，这时输出 $0$。

2. $cnt_{grass} = 1$。

$\begin{matrix} 0 & 1\\ 0 & 0\\ \end{matrix}$

显然还需要再切一次，这时输出 $1$。

3. $cnt_{grass} = 2$。

$\begin{matrix} 1 & 1\\ 0 & 0\\ \end{matrix}$

这时只用切一次。

还有一种情况：

$\begin{matrix} 0 & 1\\ 1 & 0\\ \end{matrix}$

我们只需要选择 $(2,2)$ 这个点就可以一次将其切割完。

在这种情况下，输出 $1$。

4. $cnt_{grass} = 3$。

$\begin{matrix} 1 & 1\\ 0 & 1\\ \end{matrix}$

很显然，这种情况只需要切一次，输出 $1$。

5. $cnt_{grass} = 4$。

$\begin{matrix} 1 & 1\\ 1 & 1\\ \end{matrix} \to \begin{matrix} 0 & 0\\ 1 & 0\\ \end{matrix} \to \begin{matrix} 0 & 0\\ 0 & 0\\ \end{matrix}$

所以这种情况要切三次，输出 $3$ 即可。

代码实现

#include<bits/stdc++.h>
using namespace std;
int t,tmp;
int main() {
	scanf("%d",&t);
	while(t--) {
		int sum=0;
		for(int i=1;i<=4;i++) {
			scanf("%d",&tmp);
			if(tmp) sum++;
		}
		if(sum==0) puts("0");
		else if(sum==1) puts("1");
		else if(sum==2) puts("1");
		else if(sum==3) puts("1");
		else if(sum==4) puts("2");
	}
	return 0;
}
//code by TheCedar