https://codeforces.com/contest/1194/problem/B
这道题其实是一道思维题,主要是要把情况考虑清楚,然后在代码上把逻辑理顺,就能做出来。
题目给出了cross的定义:所在行和列都全部被涂黑。
这道题分析可以知道,要对每行和每列的白色格子进行计数,然后相加。
然后,很自然的可以想到,如果行列相交的位置是白色格子,那么这个格子就被计数了两次,就需要在总数上减一。
如果白色格子不是交点的话,那就直接输出最小需要涂黑的白色格子数量就好了。
这道题我思路想出来很简单,但是在实现的时候,却总是卡在一个测试点过不了,百思不得其解。想了半天,看了测试数据,才明白问题出在我对于tmp和min_white的计算上(就是那个减不减1的问题)。
一定要每次都把当前需要涂黑的格子的数量,再和之前得出的最小值进行比较。然后更新最小值。
代码实现
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
//#include<Windows.h>
using namespace std;
int q;
string s[50005];
void solve()
{
for (int i = 0; i < q; i++)
{
int n, m;
cin >> n >> m;
int jsr_white[50001] = { 0 };
int jsc_white[50001] = { 0 };
for (int j = 0; j < n; j++)
{
cin >> s[j];
for (int k = 0; k < m; k++)
{
if (s[j][k] == '.')
{
jsr_white[j]++;
jsc_white[k]++;
}
}
}
int min_white = 999999999;
int min_j = 0, min_k = 0;
for (int j = 0; j < n; j++)
{
for (int k = 0; k < m; k++)
{
int tmp = jsr_white[j] + jsc_white[k];
if (s[j][k] == '.')
tmp--;
if (tmp < min_white)
{
min_white = tmp;
}
}
}
cout << min_white << endl;
}
}
int main()
{
cin >> q;
solve();
//system("pause");
}