Алгоритм ли?

Хотелось бы узнать как делать эту задачу, алгоритм ли тут вроде не пройдет если будет много дверей, прошу вас помочь



D. Пещера
Ограничение времени 1 секунда
Ограничение памяти 256Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
Есть карта пещеры размера N×M.

В каждой клетке может быть:

«.» (точка) — пустой участок
«$» — сокровища
«#» (решетка) — камень
заглавная буква английского алфавита — дверь
маленькая буква английского алфавита — ключ
Несложно догадаться что по камням ходить нельзя. Если вы оказываетесь в клетке с ключом, то вы можете взять его себе. С помощью ключа «a» можно открыть дверь «A», c помощью «b» можно открыть «B» и т.д. При этом на карте может находиться несколько одинаковых ключей и несколько одинаковых дверей. Изначально все двери закрыты и ходить через них нельзя. Проходить по клетке с дверью вы можете только если у вас есть ключ от этой двери, при этом после прохождения через дверь ключ остается у вас. Войти в пещеру можно в любой клетке на границе карты, в которой не находится камень или дверь, к которой у вас нет ключа. Во время путешествия можно выходить из пещеры и заходить в нее снова. Цель — как можно больше собрать сокровищ. Какое максимальное количество сокровищ вы сможете собрать при оптимальной ходьбе по пещере?

Формат ввода
Первая строка содержит два целых числа N и M (1 ≤ N, M ≤ 1000).
Следующие N строк содержат описание пещеры.
Каждая строка содержит M символов. Каждый символ это или «.», или «$», или «#», или буква английского алфавита.

Формат вывода
Выведите одно число — ответ на задачу.

Пример
Ввод Вывод
7 8
#.####.#
#.C..#a#
#A#..###
#.#....#
#.#..$$#
#$c#.$$#
########

0

Ну bfs должен справиться. Начинаешь одновременно со всех входов. Нашёл дверь и нет ключа - сохрани координату. Нашёл дверь и есть ключ - игнорируй дверь. Нашёл ключ и есть сохранённая координата соответствующая букве - закидывай её в bfs.

0