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");
	
}

欢迎关注我的公众号“灯珑”,让我们一起了解更多的事物~

你也可能喜欢

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注