Как можно оптимизировать код на C++ (задача Артефакты на киноплёнке)?
В первые годы существования кино технология изготовления киноплёнки была, что естественно, на невысоком уровне. Так что «артефакты» на экране были самым обычным делом.
После отсмотра только что снятой сцены известный байтландский режиссёр предъявил претензии поставщикам плёнки из-за большого количества артефактов на экране. Согласно договору, плёнка считается бракованной, если в некотором прямоугольнике, каждая из сторон которого параллельна сторонам экрана и имеет длину не менее m, доля артефактов превышает определённое значение. Перед встречей с представителем поставщика режиссёр хочет выяснить, чему равен максимум соответствующей доли артефактов для заданного кадра.
Формат ввода
В первой строке входа заданы три целых числа u, d и m — количество точек на экране по вертикали, количество точек на экране по горизонтали, длина стороны минимального квадрата m (1 ≤ u,d ≤ 50, 1 ≤ m ≤ min(u,d)). Следующая строка содержит от 1 до 26 попарно различных заглавных латинских букв, соответствующих артефактам на экране.
Далее следует описание кадра. Каждая из последующих u строк содержит по d заглавных латинских букв от “A” до “Z”, задающих яркость точек на экране (при этом, если буква входит в список обозначений артефактов, то в данной точке содержится артефакт).
Формат вывода
Выведите максимальную по всем прямоугольникам со сторонами m и более долю артефактов в следующем формате: количество артефактов в “максимальном” прямоугольнике, знак `/', общее количество точек в этом прямоугольнике. В случае, если максимум достигается для нескольких прямоугольников с различным количеством точек, выберите прямоугольник, в котором количество точек максимально.
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
int main()
{
int u = 0, d = 0, m = 0;
std::cin >> u >> d >> m;
std::string arts = "";
std::cin>>arts;
float max = 0.0f;
std::string kadr[u];
int ansdef = 0;
int maxs = 0;
for (int i = 0; i < u; i++)
{
std::cin>>kadr[i];
}
for (int i = m; i <= std::min(u,d); i++)
{
for (int ij = m; ij <= std::min(u,d); ij++)
{
for (int j = 0; j <= u-i; j++)
{
for (int k = 0; k <= d-ij; k++)
{
int artscur = 0;
for (int h = 0; h < i; h++)
{
for (int w = 0; w < ij; w++)
{
if (arts.find(kadr[j+h][k+w]) != std::string::npos)
{
artscur++;
}
}
}
if ((artscur*1.0f)/(i*ij) >= max)
{
max = (artscur*1.0f)/(i*ij);
ansdef = artscur;
maxs = i*ij;
}
}
}
}
}
std::cout << ansdef << "/" << maxs << "\n";
return 0;
}
Ответы (1 шт):
По представленному коду я подозреваю, что это вы же создавали вопрос на двух других форумах, но на одном из них не было полного условия... В люблюм случае, на всякий случай я предоставлю ответ.
От двух уровней вложенности можно избавиться, заранее посчитав количество артефактов в прямоугольниках. Я для этого создал дополнительную матрицу counts. counts[i][j] хранит кол-во артефактов в прямоугольнике от [0][0] до [i][j]. Кол-во артефактов в прямоугольнике от [k][l] до [i][j] можно получить по формуле:
counts[i][j] + counts[k - 1][l - 1] - counts[i][l - 1] - counts[k - 1][j]
Также не обязательно хранить строки. Вы во время чтения можете перевести входной массив строк в булевую матрицу, где 1 значит наличие артефакта в этой точке.
Наконец, std::string хранит указатели, а значит вы постоянно будете заниматься разыменовыванием, что не очень дружелюбно к кешу процессора. Лучше всего расположить все элементы в памяти подряд, поэтому я использую одномерные массивы и адресную арифметику.
Итоговый код
#include <iostream>
#include <string>
#include <cstdint>
typedef uint32_t size_type; // Для размеров массива/индексов
typedef uint32_t diff_type; // Для количества элементов в прямоугольнике
bool* input(size_type& rows, size_type& cols, size_type& min);
void find(bool* matr, size_type rows, size_type cols, size_type min, diff_type& worst_area, diff_type& worst_score);
diff_type* get_counts(bool* matr, size_type rows, size_type cols);
int main()
{
size_type rows, cols, min;
bool* matr = input(rows, cols, min);
diff_type worst_area, worst_score;
find(matr, rows, cols, min, worst_area, worst_score);
delete[] matr;
std::cout << worst_score << '/' << worst_area;
}
bool* input(size_type& rows, size_type& cols, size_type& min)
{
std::cin >> rows >> cols >> min >> std::ws;
std::string delim; std::getline(std::cin, delim);
bool* matr = new bool[rows * cols];
bool* it_matr = matr;
bool* end_matr = matr + rows * cols;
while (it_matr != end_matr)
{
char tmp; std::cin >> tmp;
bool res = delim.find(tmp) != std::string::npos;
*it_matr++ = res;
}
return matr;
}
void find(bool* matr, size_type rows, size_type cols, size_type min, diff_type& worst_area, diff_type& worst_score)
{
diff_type* counts = get_counts(matr, rows, cols);
worst_area = 1;
worst_score = 0;
for (size_type beg_row = 0; beg_row < rows; beg_row++)
{
for (size_type beg_col = 0; beg_col < cols; beg_col++)
{
for (size_type end_row = beg_row + min - 1; end_row < rows; end_row++)
{
for (size_type end_col = beg_col + min - 1; end_col < cols; end_col++)
{
diff_type count = counts[end_row * cols + end_col];
if (beg_row > 0 && beg_col > 0)
count += counts[(beg_row - 1) * cols + beg_col - 1];
if (beg_row > 0)
count -= counts[(beg_row - 1) * cols + end_col];
if (beg_col > 0)
count -= counts[end_row * cols + beg_col - 1];
diff_type area = (end_row - beg_row + 1) * (end_col - beg_col + 1);
if (count * worst_area > worst_score * area || count * worst_area == worst_score * area && count > worst_score) {
worst_area = area;
worst_score = count;
}
}
}
}
}
delete[] counts;
}
diff_type* get_counts(bool* matr, size_type rows, size_type cols)
{
diff_type* counts = new diff_type[rows * cols];
diff_type* it_counts = counts;
diff_type* end_counts = counts + rows * cols;
bool* it_matr = matr;
while (it_counts != end_counts)
{
diff_type* end_row = it_counts + cols;
*it_counts++ = *it_matr++;
while (it_counts != end_row)
*it_counts++ = *(it_counts - 1) + *it_matr++;
}
it_counts = counts + cols;
while (it_counts != end_counts)
*it_counts++ = *it_counts + *(it_counts - cols);
return counts;
}