Матч 314, Мычание коров (MooingCows)

Дивизион 2, Уровень 1

Коровы пасутся на поле прямоугольной формы, разбитой на n*m единичных квадратов. Каждый квадрат может быть или пустым, или занятым одной коровой. Корова, мычащая в позиции (x, y), создает неудовлетворение корове в позиции (i, j), равное квадрату расстояния между ними: (x - i)² + (y – j)². Всеобщее неудовлетворение равно сумме неудовлетворений для всех коров. Известно, что мычать может только одна корова.

Необходимо определить наименьшее возможное всеобщее неудовлетворение, которое может создавать одна корова.

Класс: MooingCows

Метод: int dissatisfaction(vector<string> farmland)

Ограничения: farmland содержит от 1 до 50 строк, каждая строка farmland[i] содержит до 50 символов ‘C’ и ‘.’.

Вход. Массив строк farmland, описывающий поле с коровами.

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

Пример входа

farmland

{"C..",

".C.",

".C."}

{"CCCC",

"CCCC",

"CCCC"}

{"C"}

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

3

26

0

РЕШЕНИЕ

обработка строк + элементарные вычисления

Проходим по массиву farmland и для каждой коровы вычисляем всеобщее неудовлетворение для других коров, которое она может создавать своим мычанием. Среди всех вычисленных всеобщих неудовлетворений находим наименьшее.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

using namespace std;

class MooingCows

{

public:

int dissatisfaction(vector<string> farmland)

{

int sum, res = 2000000000;

int n = farmland.size(), m = farmland[0].size();

int i, j, i1, j1;

for(i = 0; i < n; i++)

for(j = 0; j < m; j++)

if (farmland[i][j] == 'C')

{

sum = 0;

for(i1 = 0; i1 < n; i1++)

for(j1 = 0; j1 < m; j1++)

if (farmland[i1][j1] == 'C')

sum += (i1 - i) * (i1 - i) + (j1 - j) * (j1 - j);

if (sum < res) res = sum;

}

return res;

}

};