Найдите общее количество фигур 'X'

Дана сетка размером N * M, состоящая из O и X. Задача состоит в том, чтобы найти общее количество фигур 'X'.

Примечание : форма «X» состоит из одного или нескольких соседних крестиков (диагонали не включены).

Примеры :

Input: grid = {{X, O, X}, {O, X, O}, {X, X, X}}
Output: 3
Explanation: The grid is:
X O X   |   X O X   |  X O X 
O X O  |   O X O   |  O X O
X X X   |   X X X    |  X X X
So, X with bold color are adjacent to each other vertically for horizontally (diagonals not included). So, there are 3 different groups in the given grid.

Input: grid = {{X, X}, {X, X}}
Output: 1
Explanation: The grid is: 
X X
X X
So, X with bold color are adjacent to each other vertically for horizontally (diagonals not included). So, there is only 1 group in the given grid.

Подход : Чтобы решить проблему, следуйте следующей идее:

The idea is to apply dfs from every cell having ‘X’ and not visited, mark all its adjacent cells visites if their value is X and increase the answer by one.

Следуйте инструкциям, чтобы решить эту проблему:

• Вместо использования дополнительного вектора vis размером n*m для отслеживания того, какая ячейка посещается, а какая нет, мы можем просто преобразовать посещенную ячейку, имеющую «X», в «O».
• Инициализируйте переменную с помощью 0, она будет вести подсчет подключенных компонентов, имеющих только « X ».
• Создайте функцию dfs (x, y), чтобы пометить весь подключенный компонент, имеющий только «X», как посещенный, преобразовав все «X» в «O».
• Запустите 2 вложенных цикла для перебора всей сетки.
  • Проверьте, имеет ли текущая ячейка « X », затем запустите из нее dfs и преобразуйте все ячейки в ее подключенном компоненте как «O» и
  • Увеличьте переменную ans на 1.
• Вернуть переменную ans в качестве ответа.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N * M), так как векторная сетка имеет N * M ячеек, и каждая ячейка посещается максимум один раз.
Вспомогательное пространство: O (1). Если рассматривать стек рекурсии, временная сложность составляет O (N * M)

Статьи по Теме:

• Введение в матрицу или сетку - учебные пособия по структурам данных и алгоритмам
• Поиск в глубину или DFS для графика