Прямоугольники в квадрате. На квадратном клетчатом листе бумаги размером 100x100 клеток нарисовано несколько прямоугольников. Каждый прямоугольник состоит из целых клеток, различные прямоугольники не накладываются друг на друга и не соприкасаются.
Задан массив размером 100*100, в котором элемент A[i, j]=1, если клетка [i, j] принадлежит какому-либо прямоугольнику, и A[i, j]=0 в противном случае. Написать программу, которая сосчитает и напечатает число прямоугольников.
C/C++
Программирование на С++
#include < iostream >
#include < vector >
#include < map >
using namespace std;
map < int, bool > cash;
void input(vector < vector< int > > &map) // ввод поля еденицами и нулями
{
cout << "Fill the map 0 and 1: \n";
for (vector < int > &i : map)
for (int &j : i) cin >> j;
}
void fill(vector < vector < int > > & map, int x_coord, int y_coord, int &number)
{
map[x_coord][y_coord] = number;
int iterator = 1; // направление итератора 1 - направо, -1 налево.
while (true)
{
if (y_coord + iterator < map[x_coord].size() && y_coord + iterator >= 0 && map[x_coord][y_coord + iterator] != 0) { //идем вправо до упора
y_coord += iterator; map[x_coord][y_coord] = number;
}
else
if (x_coord + 1 < map.size() && map[x_coord + 1][y_coord] != 0) { x_coord++; map[x_coord][y_coord] = number; iterator *= -1; continue; } //если тупик смотрим вниз, если место есть.
//спускаемся, заполняем, меняем итератор, возвращаемся к началу цикла
else { cash[number] = true; number++; return; } // после заполнения почемяем текущий номер как посчитанный и увеличиваем его.
}
}
int main()
{
int x, y;
cout << "Enter sizes x,y:\n";
cin >> x >> y;
vector <vector < int > > map(x, vector < int > (y));
input(map);
int count = 2; // 1 и 0 заняты, начинаем счет фигур с 2. В итоге просто отнимем 2 от числа.
for (int i = 0; i<x; i++)
for (int j = 0; j < y; j++)
{
if (!cash.count(map[i][j]) && map[i][j] != 0) //если найдена непустая неподсчитанная клетка
fill(map, i, j, count); //заполняем весь смежный квадрат
}
cout << endl << "count of figures = " << count - 2;
}
#include < vector >
#include < map >
using namespace std;
map < int, bool > cash;
void input(vector < vector< int > > &map) // ввод поля еденицами и нулями
{
cout << "Fill the map 0 and 1: \n";
for (vector < int > &i : map)
for (int &j : i) cin >> j;
}
void fill(vector < vector < int > > & map, int x_coord, int y_coord, int &number)
{
map[x_coord][y_coord] = number;
int iterator = 1; // направление итератора 1 - направо, -1 налево.
while (true)
{
if (y_coord + iterator < map[x_coord].size() && y_coord + iterator >= 0 && map[x_coord][y_coord + iterator] != 0) { //идем вправо до упора
y_coord += iterator; map[x_coord][y_coord] = number;
}
else
if (x_coord + 1 < map.size() && map[x_coord + 1][y_coord] != 0) { x_coord++; map[x_coord][y_coord] = number; iterator *= -1; continue; } //если тупик смотрим вниз, если место есть.
//спускаемся, заполняем, меняем итератор, возвращаемся к началу цикла
else { cash[number] = true; number++; return; } // после заполнения почемяем текущий номер как посчитанный и увеличиваем его.
}
}
int main()
{
int x, y;
cout << "Enter sizes x,y:\n";
cin >> x >> y;
vector <vector < int > > map(x, vector < int > (y));
input(map);
int count = 2; // 1 и 0 заняты, начинаем счет фигур с 2. В итоге просто отнимем 2 от числа.
for (int i = 0; i<x; i++)
for (int j = 0; j < y; j++)
{
if (!cash.count(map[i][j]) && map[i][j] != 0) //если найдена непустая неподсчитанная клетка
fill(map, i, j, count); //заполняем весь смежный квадрат
}
cout << endl << "count of figures = " << count - 2;
}
Похожие вопросы
- Программирование на С++
- Программирование на C++
- Как начать изучать программирование?
- Доброго дня! Хочу сменить сферу деятельности . Заинтересовал вариант программирования .
- Программирование на C++
- Книги по программированию.
- Может ли новичок в программирование начать с c++/Gamedev
- Чем отличаются языки программирования ???
- На каком языке программирования (Assembler / С / С++) лучше будет написать компилятор для своего языка программирования?
- Указатели. Программирование с использованием динамических двухмерным масивов.