Задача:
Рассмотрим бесконечный лист клетчатой бумаги. Закрасим некоторое множество клеток в черный цвет. Теперь мы хотим закрасить минимальное количество клеток, так, чтобы множество черных клеток стало выпуклым.
Напомним, что геометрическая фигура Φ называется выпуклой, если для любых точек A из Φ и В из Φ с вещественными координатами отрезок [AB] принадлежит Φ.
Входные данные
В первой строке входного файла INPUT.TXT содержатся два числа N и M (1 ≤ N, M ≤ 100) — размеры куска бумаги, куда попали все черные клетки. В каждой из следующих N строк содержится М символов «*» или «.». Символ «*» обозначает черную клетку, а «.» белую.
Выходные данные
В выходной файл OUTPUT.TXT выведите выпуклое множество, содержащее минимальное количество дополнительно покрашенных черных клеток, в ровно N строках по M символов «*» или «.» в каждой.
Примеры
Вход:
2 4
..*.
.**.
Выход:
.**.
.**.
Вход:
4 3
.*.
.*.
.*.
.*.
Выход:
.*.
.*.
.*.
.*.
Большинство входных данных обрабатывается верно, но при попытке сдать на сайте появляются неверные ответы.
Идея: найти минимальные и максимальные строки и колонки, в которых находится символ звёздочки, затем вывести то, что находится внутри найденных границ, со звёздочками, а остальное - с точками.
#include <iostream>
#include <fstream>
#include <string>
int main()
{
int rows = 0, columns = 0;
std::ifstream file("INPUT.txt");
std::cin >> rows;
std::cin >> columns;
int rMax = 0, rMin = 101, cMax = 0, cMin = 101;
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < columns; j++)
{
char c;
file >> c;
if (c == '*' && i < rMin)
{
rMin = i;
}
if (c == '*' && i > rMax)
{
rMax = i;
}
if (c == '*' && j < cMin)
{
cMin = j;
}
if (c == '*' && j > cMax)
{
cMax = j;
}
}
}
file.close();
std::ofstream fout("OUTPUT.txt");
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < columns; j++)
{
if (i >= rMin && rMax >= i && cMax >= j && cMin <= j)
{
fout << "*";
}
else
{
fout << ".";
}
}
fout << std::endl;
}
fout.close();
}
