Я не могу понять, как подойти к этой проблеме, любая помощь будет высоко ценится.
https://leetcode.com/discuss/interview-question/580062/Field-of-dreams
Поле снов
Поле представлено двумерной сеткой размером NxM. Каждая ячейка в сетке является либо ячейкой ag, либо рекламной ячейкой, где g обозначает траву, а d обозначает грязь. Говорят, что две ячейки связаны, если они имеют общий край. Сетка называется подключенным, если все g-клетки можно пройти без прохождения через d-клетки. В противном случае сетка считается отключенной. Напишите программу, чтобы найти минимальное количество g ячеек, которые должны быть заменены на d ячеек, чтобы сетка была отключена. Если сетка изначально отключена, выведите 0.
Формат ввода
Первая строка N и M Следующие N строк: M символов, разделенных пробелами (g или d) Формат вывода Выведите минимальное количество g ячейки, которые должны быть заменены на d ячеек, так что сетка отключена. Если сетка изначально отключена, выведите 0.
Ограничения 1 <= NM <= 400 </p>
Пример ввода ggg gdg ggg
Пример вывода 2
Пояснение
Вы можете преобразовать 2 g в d, чтобы преобразовать сетку в следующее:
ggd gdg dgg
Сетка больше не подключена.