LOJ 6030（雅礼集训2017 Day1）矩阵（乱搞）

发表于 |
字数统计: 637字 | 阅读时长 ≈ 3min

「雅礼集训 2017 Day1」矩阵

问题描述

有一个 $ n \times n $ 的矩阵，每个位置 $ (i, j) $ 如果是 . 表示为白色，如果是 # 表示为黑色。

初始时，每个位置可以是黑色或白色的，$ (i, j) $ 位置的值会作为 $ a_{i, j} $ 给你。

现在有一种操作，选择两个整数 $ i, j \in [1, n] $，记 $ (i, 1), (i, 2), \ldots, (i, n) $ 的颜色为 $ C_1, C_2, \ldots C_n $，将 $ (1, j), (2, j), \ldots, (n, j) $ 的颜色赋为 $ C_1, C_2, \ldots, C_n $。

你的任务是将整个矩阵变成全黑，如果能够办到，输出最少步数，否则输出 $ -1 $。

输入格式

第一行一个整数 $ n $。

接下来 $ n $ 行，每行 $ n $ 个字符表示整个矩阵。

输出格式

输出只有一行，一个整数表示答案。

样例输入

2
#.
.#

样例输出

3

提示

对于 $ 30\% $ 的数据，$ n \leq 4 $；

对于另外 $ 20\% $ 的数据，满足每一列都至少有一个黑色的格子；

对于 $ 100\% $ 的数据，$ 1 \leq n \leq 1000 $。

容易发现题目无解当且仅当该矩阵全白。

容易发现最优解一定是先得到全黑的一行。

因此我们考虑直接枚举将哪一行变成全黑，容易发现要将第$i$行变成全黑，需要第$i$列有一个黑色格子，并且每次只能使一个位置变黑。

因此我们只需要算算初始有多少行，多少列是全黑，然后枚举将哪一行变成全黑，然后取最小值就行了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 1005
using namespace std;
char map[N][N];
int n,cntx,cnty;
bool No=1;
int Calx()
{
	for(int i=1;i<=n;i++)
	{
		int k=1;
		for(int j=1;j<=n;j++)if(map[i][j]=='.')k=0;
		cntx+=k;
	}
}
int Caly()
{
	for(int i=1;i<=n;i++)
	{
		int k=1;
		for(int j=1;j<=n;j++)if(map[j][i]=='.')k=0;
		cnty+=k;
	}
}
int Cal(int x)
{
	int i,j,k=1,cnt=0;
	for(i=1;i<=n;i++)if(map[i][x]=='#')k=0;
	for(i=1;i<=n;i++)cnt+=map[x][i]=='.';
	return cnt+k;
}
int main()
{
	int i,j,k,Min=1e9;
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%s",&map[i][1]);
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)if(map[i][j]=='#')No=0;
	if(No)return puts("-1"),0;
	Calx();Caly();
	if(cntx==n)return puts("0"),0;
	if(cntx!=0)return printf("%d",n-cnty),0;
	for(i=1;i<=n;i++)Min=min(Min,Cal(i)+n-cnty);
	printf("%d",Min);
}