Матч 33, Охранники замка (CastleGuards)

Имеется прямоугольный замок, первый этаж которого охраняется стажей. Элемент castle[i][j] содержит ‘.’, если поле (i, j) свободно, и содержит ‘X’, если в позиции (i, j) находится охранник. В каждой строке и каждом столбце массива castle, описывающего замок, должно находиться хотя бы по одному охраннику. Необходимо добавить наименьшее количество охранников, чтобы выполнялось приведенное выше условие.

Класс: CastleGuards

Метод: int missing(vector<string> castle)

Ограничения: castle содержит от 1 до 50 строк, каждая из которых содержит от 1 до 50 символов ‘.’ и ‘X’.

Вход. Массив строк castle, описывающий состояние замка.

Выход. Наименьшее количество охранников, которое нужно добавить чтобы в каждой строке и каждом столбце массива castle находился хотя бы один охранник.

Пример входа

castle

{"....",

"....",

"....",

"...."}

{"....XXXX",

"........",

"XX.X.XX.",

"........",

"........"}

{"XX...",

".XX..",

"...XX"}

Пример выхода

4

3

0

РЕШЕНИЕ

обработка строк

Находим количество строк c1 и количество столбцов c2, в которых нет ни одного охранника. Искомое количество охранников, которое нужно добавить, равно max(c1, c2).

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

#include <numeric>

using namespace std;

int f(int a, char b)

{

return a + (b == 'X');

}

class CastleGuards

{

public:

int missing(vector<string> castle)

{

int i, j, flag, c1, c2;

for(c1 = i = 0; i < castle.size(); i++)

c1 += !accumulate(castle[i].begin(),castle[i].end(),0,f);

for(c2 = i = 0; i < castle[0].size(); i++)

{

flag = 1;

for(j = 0; j < castle.size(); j++)

if (castle[j][i] == 'X') flag = 0;

c2 += flag;

}

return (c1 > c2) ? c1 : c2;

}

};