题目概述

Q老师 得到一张 n 行 m 列的网格图，上面每一个格子要么是白色的要么是黑色的。5
Q老师认为失去了 十字叉 的网格图莫得灵魂. 一个十字叉可以用一个数对 x 和 y 来表示, 其中 1 ≤ x ≤ n 并且 1 ≤ y ≤ m, 满足在第 x 行中的所有格子以及在第 y 列的 所有格子都是黑色的
例如下面这5个网格图里都包含十字叉

第四个图有四个十字叉，分别在 (1, 3), (1, 5), (3, 3) 和 (3, 5).

下面的图里没有十字叉
Q老师 得到了一桶黑颜料，他想为这个网格图注入灵魂。 Q老师 每分钟可以选择一个白色的格子并且把它涂黑。现在他想知道要完成这个工作，最少需要几分钟？

输入样例

第一行包含一个整数 q (1 ≤ q ≤ 5 * 10^4) — 表示测试组数
对于每组数据：
第一行有两个整数 n 和 m (1 ≤ n, m ≤ 5 * 10^4, n * m ≤ 4 * 10^5) — 表示网格图的行数和列数
接下来的 n 行中每一行包含 m 个字符 — ‘.’ 表示这个格子是白色的， '’ 表示这个格子是黑色的
保证 q 组数据中 n 的总和不超过 5 * 10^4， nm 的总和不超过 4 * 10^5

9
5 5
..*..
..*..
*****
..*..
..*..
3 4
****
.*..
.*..
4 3
***
*..
*..
*..
5 5
*****
*.*.*
*****
..*.*
..***
1 4
****
5 5
.....
..*..
.***.
..*..
.....
5 3
...
.*.
.*.
***
.*.
3 3
.*.
*.*
.*.
4 4
*.**
....
*.**
*.**

输出样例

答案输出 q 行, 第 i 行包含一个整数 — 表示第 i 组数据的答案

0
0
0
0
0
4
1
1
2

思路概述

题目给定了一种定义：要求的状态是在图中有一个十字叉（即在某行某列上完全被涂色）
题目的要求即给定一个图，求出最少涂色的块数使图成为一个要求的状态图。
通过观察我们发现，无论十字叉在哪个位置，中心位置即行和列的交点只有一个，因此一个十字叉可以使用中心的点来唯一标识。
清楚了这个思路，进行求解只需要两个步骤：
1、在输出图时，计数每一行和每一列有多少个涂色块，并记录下每个点的涂色情况。
2、对行列的点进行枚举，计算需要涂色形成十字叉的公式如下：
当该中心点涂上了色时

			需要涂色的块数=n+m-1-(m_record[i]+n_record[j]-1));

当该中心点没上色时

			需要涂色的块数=n+m-1-(m_record[i]+n_record[j]));

这里的n，m是行列数，m_record和n_record是该行和该列上有多少个涂色了的块。
套入公式取最小值即可

实现代码（C++）

#include<iostream>
#include<stdio.h>
#include<string.h>using namespace std;
const int M=5e4+5;
const int N=4e5+5;
const int MAX_INT=1e9+5;int data_group;
int m;
int n;
int m_record[M];
int n_record[M];
int flag[N];
char a;
int res;
int main()
{scanf("%d",&data_group);for(int k=0;k<data_group;k++){res=MAX_INT;scanf("%d %d",&m,&n);memset(m_record,0,M);memset(n_record,0,M);memset(flag,0,N);getchar();for(int i=0;i<m;i++){for(int j=0;j<n;j++){scanf("%c",&a);if(a=='*'){m_record[i]++;n_record[j]++;flag[i*n+j]=1;}}getchar();}for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(flag[i*n+j]==1)res=min(res,n+m-1-(m_record[i]+n_record[j]-1));elseres=min(res,n+m-1-(m_record[i]+n_record[j]));}}printf("%d\n",res);}return 0;
}