Здраствуйте, Помогите с програмированием пожалуйста!!!
Приветствуется решение на любом языке програмирования.
Дана прямоугольная таблица A размера N × M . В ней требуется посчитать, сколько связных фигур из закрашенных клеток образуют прямоугольники. Связная фигура — фигура из соединенных между собой закрашенных клеток, соседних по сторонам. Прямоугольник должен быть со всех сторон окружен пустыми клетками или границами поля.
Формат ввода
В первой строке входных данных записаны два числа
N и M ( 1 ≤ N , M ≤ 2000) — размеры матрицы A . В каждой из следующих N строк записано M символов A i, j , равных ‘#’ (ASCII код 35) или ‘.’ (ASCII код 46), символ ‘#’ означает закрашенную клетку, ‘.’ - пустую.
Формат вывода
Выведите одно число: число закрашенных прямоугольников в исходной матрице.
#include <iostream>
#include <vector>
using namespace std;
vector<vector<char>> grid;
int n, m;
void dfs(int i, int j) {
if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] == '.' )
return;
grid[i][j] = '.';
dfs(i - 1, j);
dfs(i + 1, j);
dfs(i, j - 1);
dfs(i, j + 1);
}
int countRectangles() {
int count = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == '#') {
++count;
dfs(i, j);
}
}
}
return count;
}
int main() {
cin >> n >> m;
grid.resize(n, vector<char>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> grid[i][j];
}
}
cout << countRectangles() << endl;
return 0;
}
Этот код считывает матрицу, затем запускает алгоритм поиска в глубину из каждой клетки, закрашенной символом "#", и подсчитывает количество связанных фигур.
Для начала, давайте разберемся, как мы можем подсчитать количество закрашенных прямоугольников в данной матрице. Мы можем использовать алгоритм обхода графа (например, поиск в глубину или поиск в ширину), чтобы найти связные фигуры из закрашенных клеток. Затем мы проверим, можно ли образовать из них прямоугольник.
Вот план решения:
Создадим функцию для обхода связных фигур (например, поиск в глубину).
Пройдемся по всей матрице и для каждой закрашенной клетки вызовем функцию обхода связных фигур.
Внутри функции обхода связных фигур будем искать все закрашенные клетки, которые принадлежат одной связной фигуре.
Если количество закрашенных клеток в связной фигуре больше 1, проверим, можно ли из них образовать прямоугольник (то есть, есть ли закрашенные клетки сверху, снизу, слева и справа от текущей клетки).
Если можно, увеличим счетчик прямоугольников.