Дискретка 2 сем. 2 лаб. E

podsolnyxxx

May 18th, 2024

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 1.86 KB | None | 0 0

raw download clone embed print report

#include <iostream>
#include <vector>
using namespace std;
// Функция для проверки корректности координат и значения клетки
bool isValid(int x, int y, int M, int N, const vector<vector<char>>& grid, vector<vector<bool>>& visited) {
return (x >= 0 && x < M && y >= 0 && y < N && grid[x][y] == '#' && !visited[x][y]);
}
// Функция для выполнения DFS
void dfs(int x, int y, int M, int N, const vector<vector<char>>& grid, vector<vector<bool>>& visited) {
// Направления движения: вверх, вниз, влево, вправо
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
// Помечаем текущую клетку как посещенную
visited[x][y] = true;
// Рекурсивно посещаем все соседние клетки
for (int i = 0; i < 4; ++i) {
int newX = x + dx[i];
int newY = y + dy[i];
if (isValid(newX, newY, M, N, grid, visited)) {
dfs(newX, newY, M, N, grid, visited);
}
}
}
int main() {
int M, N;
cin >> M >> N;
vector<vector<char>> grid(M, vector<char>(N));
// Считываем матрицу
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
cin >> grid[i][j];
}
}
vector<vector<bool>> visited(M, vector<bool>(N, false));
int components = 0;
// Поиск всех компонентов
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (grid[i][j] == '#' && !visited[i][j]) {
dfs(i, j, M, N, grid, visited);
components++;
}
}
}
// Вывод количества компонентов
cout << components << endl;
return 0;
}

Add Comment

Please, Sign In to add comment