0

Здравствуйте. Есть задача "Военная база":

Со спутника-шпиона получено изображение в некотором волновом диапазоне сверхсекретной военной базы предполагаемого противника. База расположена на Антарктиде, все постройки на ней высечены из кубов льда и имеют на фотографии квадратную форму и не имеют общих фрагментов стен ненулевой длины (по всей видимости, это сделано в целях маскировки от локаторов, работающих в инфракрасном спектре). Благодаря мастерству операторов оказалось, что стены разных построек параллельны границам фотографии.

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

Входные данные

В первой строке входного файла INPUT.TXT записаны числа N и M (1 <= M, N <= 500) – размеры фотографии в пикселях по вертикали и по горизонтали. Следующие N строк содержат по M символов каждая: символ '.' соответствует пустому месту, '#' – элементу постройки.

Выходные данные

В выходной файл OUTPUT.TXT выведите единственное число – количество построек на базе.

Идей, как её написать, нет. Уместен ли тут поиск в ширину? Напишите реализацию поиска в ширину и глубину в двумерном массиве. Спасибо.

1
  • @username76 Почитайте на e-maxx.ru про обходы в ширину и глубину
    – andrybak
    24 дек 2011 в 16:39

2 ответа 2

1

Обходишь все элементы массива по порядку при этом выполняя следующее: проверяешь является ли элемент стеной, если да то проверяешь 4 элемента массива по сторонам света (4 штуки) если какой-либо элемент массива имеет индексацию, то присваеваешь текущему элементу этот индекс, если нет то присваеваешь текущий индекс и при этом инкрементируешь его. Количество на выходе будет индекс - 1.

0

Слабо вижу как можно использовать поиск в ширину или в глкбину, это же не древовидная тсруктура. Сходу могу предложить такое решение: считываете строки, в строке ищете символы "#" только если их несколько, это означает начало постройки (стена). Дальше считываете новую строку, ищете в ней тоже самое. Если нашли, значит постройка закончилась, инкрементируете счетчик. Можно завести какой-нибудь вектор, куда складывать начало и конец стены и проверять эти же коррдинаты в векторе после каждого считывания.

3
  • почему не древовидная? очень даже древовидная
    – andrybak
    24 дек 2011 в 19:01
  • @username76 обычно поиск в ширину на двумерном поле (лабиринты и т.п.) называют "волновым алгоритмом" или "методом заливки", а писать код за Вас тут никто не будет
    – andrybak
    24 дек 2011 в 19:03
  • Спасибо, я и не просил полностью написать за меня.
    – username76
    25 дек 2011 в 6:40

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.