На клеточном листе бумаги размером MхN расположены прямоугольники. Задан массив MхN в котором элемент а [i,j]=1 если клетка листа (i,j) яв-ся частью прямоугольника, и а [i,j]=0 если это пустая клетка. Напечатать число прямоугольников
прямоугольники могут пересекаться? если нет, посчитайте количество углов. разделите на 4, будет вам количество прямоугольников
Программа решается элементарно использую волновой алгоритм.
/////////////////////////////////////////////////////////////////////////////////////////
//На клеточном листе бумаги размером MхN расположены прямоугольники.
//Задан массив MхN в котором элемент a[i,j]=1 если клетка листа (i,j)
//яв-ся частью прямоугольника, и a[i,j]=0 если это пустая клетка.
//Напечатать число прямоугольников.
/////////////////////////////////////////////////////////////////////////////////////////
//В моей реализации нули и единицы в исходный файл записывать без пробелов.
/////////////////////////////////////////////////////////////////////////////////////////
#include
#include
#include
#include
#include
#include
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string T_str;
typedef std::vector T_strings;
/////////////////////////////////////////////////////////////////////////////////////////
bool is_left_upper_corner
(
const T_strings& strings,
int i,
int j
)
{
return strings[j] == '1'
&& (
i == 0
|| strings[i - 1][j] == '0'
)
&& (
j == 0
|| strings[j - 1] == '0'
);
}
/////////////////////////////////////////////////////////////////////////////////////////
void count_rectangles
(
const T_str& ifilename,
const T_str& ofilename
)
{
std::ifstream ifile( ifilename.c_str() );
if( !ifile )
{
std::cout
⇢