Решение задачи Очередная задача про кресты с Codeforces

С пояснением   Просмотров: 937

Вам задана картинка, состоящая из n строк и m столбцов. Строки пронумерованы от 1 по n сверху вниз, столбцы — от 1 по m слева направо. Каждая клетка раскрашена в черный или белый цвет.

Вам кажется, что данная картинка недостаточно интересна. Вы считаете, что картинка интересная, если на ней изображен хотя бы один крест. Крест представляет из себя пару чисел x и y, где 1≤x≤n и 1≤y≤m, такие, что все клетки в строке x и все клетки в столбце y черного цвета.

Например, каждое из следующих изображений содержит кресты:


Четвертая картинка содержит 4 креста: в (1,3), (1,5), (3,3) и (3,5).

Следующие изображения не содержат крестов:


У вас имеется кисточка и банка черной краски и вы можете сделать вашу картинку интересней. Каждую минуту вы можете выбрать одну белую клетку и перекрасить ее в черный.

Какое минимальное количество минут вы должны потратить, чтобы в результате картинка стала содержать хотя бы один крест?

Обратите внимание, что вам нужно будет отвечать на несколько независимых запросов.

Код 

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;


int main() {
	int q;
	cin >> q;
	forn(_, q){
		int n, m;
		cin >> n >> m;
		vector<string> s(n);
		forn(i, n)
			cin >> s[i];
		vector<int> cntn(n), cntm(m);
		forn(i, n) forn(j, m){
			cntn[i] += (s[i][j] == '.');
			cntm[j] += (s[i][j] == '.');
		}
		int ans = n + m;
		forn(i, n) forn(j, m){
			ans = min(ans, cntn[i] + cntm[j] - (s[i][j] == '.'));
		}
		cout << ans << "\n";
	}
	return 0;
}

         

Администратор Photo Автор: Администратор


Пояснение к задаче

Попробуем выбрать каждую точку центром креста, ответом будет такая из них, перекрашивание для которой занимает минимальное время. Считать каждый раз в лоб займет суммарно O(nm(n+m)), что слишком медленно. Заметим, что ответ для некоторой клетки (x,y) можно представить как cntrow[x]+cntcolumn[y]− (1, если a[x][y] белая, иначе 0), где cntrow[i] — это количество белых клеток в строке i, а cntcolumn[i] — то же для столбца i. Первые два слагаемых можно посчитать заранее.

Асимптотика решения: O(nm) на запрос.


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp