PrepBro
← Назад к вопросам

Подсчёт кораблей в игре Морской бой

1.7 Middle🔥 111 комментариев
#Стандарты разработки

Условие

Напишите функцию подсчёта количества кораблей на игровом поле в игре "Морской бой".

Поле представлено двумерным массивом, где:

  • 0 — пустая клетка
  • 1 — клетка с частью корабля

Корабли могут располагаться только вертикально или горизонтально (не по диагонали). Корабли не касаются друг друга.

Пример

Вход:

0 1 0 0 0
0 1 0 1 1
0 0 0 0 0
1 1 1 0 1
0 0 0 0 1

Выход: 4 (четыре корабля)

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Решение

Обзор задачи

Эта задача требует подсчёта связанных компонентов в двумерной сетке — классическая задача компьютерной геометрии и графов. Корабль — это набор смежных единиц, расположенных только горизонтально или вертикально. Не диагональные соседи не считаются связанными. Каждый новый связный компонент из единиц — это один корабль.

Это тест на понимание:

  • Двумерных массивов (матриц)
  • Поиска в глубину (DFS) или в ширину (BFS)
  • Работы с соседствами в сетке
  • Маркировки посещённых клеток

Математическая логика

Алгоритм:

  1. Итерируем по всем клеткам поля
  2. Если находим 1 и она не посещена — это новый корабль
  3. Отмечаем все связанные с ней единицы как посещённые (DFS или BFS)
  4. Увеличиваем счётчик кораблей
  5. Продолжаем до конца поля

Реализация 1: DFS (поиск в глубину)

Функция ПодсчитатьКораблиDFS(Поле)
    КоличествоСтрок = Поле.Количество();
    Если КоличествоСтрок = 0 Тогда
        Возврат 0;
    КонецЕсли;
    
    КоличествоКолонок = Поле[0].Количество();
    Если КоличествоКолонок = 0 Тогда
        Возврат 0;
    КонецЕсли;
    
    // Создаём матрицу посещённости
    Посещённые = Новый Массив(КоличествоСтрок);
    Для И = 0 По КоличествоСтрок - 1 Цикл
        Посещённые[И] = Новый Массив(КоличествоКолонок);
        Для Й = 0 По КоличествоКолонок - 1 Цикл
            Посещённые[И][Й] = Ложь;
        КонецЦикла;
    КонецЦикла;
    
    КоличествоКораблей = 0;
    
    // Проходим по всем клеткам
    Для Строка = 0 По КоличествоСтрок - 1 Цикл
        Для Колонка = 0 По КоличествоКолонок - 1 Цикл
            
            // Если нашли непосещённую единицу — это новый корабль
            Если Поле[Строка][Колонка] = 1 И НЕ Посещённые[Строка][Колонка] Тогда
                // Запускаем DFS для отметки всех частей корабля
                ОбойтиКорабльDFS(Поле, Посещённые, Строка, Колонка);
                КоличествоКораблей = КоличествоКораблей + 1;
            КонецЕсли;
            
        КонецЦикла;
    КонецЦикла;
    
    Возврат КоличествоКораблей;
КонецФункции

Процедура ОбойтиКорабльDFS(Поле, Посещённые, Строка, Колонка)
    КоличествоСтрок = Поле.Количество();
    КоличествоКолонок = Поле[0].Количество();
    
    // Проверяем границы
    Если Строка < 0 ИЛИ Строка >= КоличествоСтрок 
        ИЛИ Колонка < 0 ИЛИ Колонка >= КоличествоКолонок 
        ИЛИ Посещённые[Строка][Колонка] 
        ИЛИ Поле[Строка][Колонка] = 0 Тогда
        Возврат;
    КонецЕсли;
    
    // Отмечаем как посещённую
    Посещённые[Строка][Колонка] = Истина;
    
    // Проверяем четырёх соседей (вверх, вниз, влево, вправо)
    ОбойтиКорабльDFS(Поле, Посещённые, Строка - 1, Колонка);  // Вверх
    ОбойтиКорабльDFS(Поле, Посещённые, Строка + 1, Колонка);  // Вниз
    ОбойтиКорабльDFS(Поле, Посещённые, Строка, Колонка - 1);  // Влево
    ОбойтиКорабльDFS(Поле, Посещённые, Строка, Колонка + 1);  // Вправо
КонецПроцедуры

Реализация 2: BFS (поиск в ширину) — итеративный

Функция ПодсчитатьКораблиBFS(Поле)
    КоличествоСтрок = Поле.Количество();
    Если КоличествоСтрок = 0 Тогда
        Возврат 0;
    КонецЕсли;
    
    КоличествоКолонок = Поле[0].Количество();
    Если КоличествоКолонок = 0 Тогда
        Возврат 0;
    КонецЕсли;
    
    // Матрица посещённости
    Посещённые = Новый Массив(КоличествоСтрок);
    Для И = 0 По КоличествоСтрок - 1 Цикл
        Посещённые[И] = Новый Массив(КоличествоКолонок);
        Для Й = 0 По КоличествоКолонок - 1 Цикл
            Посещённые[И][Й] = Ложь;
        КонецЦикла;
    КонецЦикла;
    
    КоличествоКораблей = 0;
    
    // Проходим по всем клеткам
    Для Строка = 0 По КоличествоСтрок - 1 Цикл
        Для Колонка = 0 По КоличествоКолонок - 1 Цикл
            
            // Если нашли непосещённую единицу — это новый корабль
            Если Поле[Строка][Колонка] = 1 И НЕ Посещённые[Строка][Колонка] Тогда
                // Запускаем BFS для отметки всех частей корабля
                ОбойтиКорабльBFS(Поле, Посещённые, Строка, Колонка);
                КоличествоКораблей = КоличествоКораблей + 1;
            КонецЕсли;
            
        КонецЦикла;
    КонецЦикла;
    
    Возврат КоличествоКораблей;
КонецФункции

Процедура ОбойтиКорабльBFS(Поле, Посещённые, СтартовоеСтрока, СтартовоеКолонка)
    Очередь = Новый Массив();
    Очередь.Добавить(Новая Структура("Строка, Колонка", СтартовоеСтрока, СтартовоеКолонка));
    
    КоличествоСтрок = Поле.Количество();
    КоличествоКолонок = Поле[0].Количество();
    
    Пока Очередь.Количество() > 0 Цикл
        // Извлекаем из начала очереди (FIFO)
        Текущая = Очередь[0];
        Очередь.Удалить(0);
        
        Строка = Текущая.Строка;
        Колонка = Текущая.Колонка;
        
        // Проверяем границы и посещённость
        Если Строка < 0 ИЛИ Строка >= КоличествоСтрок 
            ИЛИ Колонка < 0 ИЛИ Колонка >= КоличествоКолонок 
            ИЛИ Посещённые[Строка][Колонка] 
            ИЛИ Поле[Строка][Колонка] = 0 Тогда
            Продолжить;
        КонецЕсли;
        
        // Отмечаем как посещённую
        Посещённые[Строка][Колонка] = Истина;
        
        // Добавляем четырёх соседей в очередь
        Очередь.Добавить(Новая Структура("Строка, Колонка", Строка - 1, Колонка));  // Вверх
        Очередь.Добавить(Новая Структура("Строка, Колонка", Строка + 1, Колонка));  // Вниз
        Очередь.Добавить(Новая Структура("Строка, Колонка", Строка, Колонка - 1));  // Влево
        Очередь.Добавить(Новая Структура("Строка, Колонка", Строка, Колонка + 1));  // Вправо
    КонецЦикла;
КонецПроцедуры

Реализация 3: С дополнительной информацией

Функция ПодсчитатьКораблиСДанными(Поле)
    КоличествоСтрок = Поле.Количество();
    Если КоличествоСтрок = 0 Тогда
        Возврат Новая Структура("КоличествоКораблей, Подробности", 0, Новый Массив());
    КонецЕсли;
    
    КоличествоКолонок = Поле[0].Количество();
    Если КоличествоКолонок = 0 Тогда
        Возврат Новая Структура("КоличествоКораблей, Подробности", 0, Новый Массив());
    КонецЕсли;
    
    Посещённые = Новый Массив(КоличествоСтрок);
    Для И = 0 По КоличествоСтрок - 1 Цикл
        Посещённые[И] = Новый Массив(КоличествоКолонок);
        Для Й = 0 По КоличествоКолонок - 1 Цикл
            Посещённые[И][Й] = Ложь;
        КонецЦикла;
    КонецЦикла;
    
    КоличествоКораблей = 0;
    Подробности = Новый Массив();
    
    Для Строка = 0 По КоличествоСтрок - 1 Цикл
        Для Колонка = 0 По КоличествоКолонок - 1 Цикл
            
            Если Поле[Строка][Колонка] = 1 И НЕ Посещённые[Строка][Колонка] Тогда
                // Подсчитываем клетки в корабле
                КоличествоКлеток = ПолучитьВеличинуКорабля(Поле, Посещённые, Строка, Колонка);
                
                Подробности.Добавить(Новая Структура(
                    "Номер, Размер",
                    КоличествоКораблей + 1,
                    КоличествоКлеток
                ));
                
                КоличествоКораблей = КоличествоКораблей + 1;
            КонецЕсли;
            
        КонецЦикла;
    КонецЦикла;
    
    Возврат Новая Структура(
        "КоличествоКораблей, Подробности",
        КоличествоКораблей,
        Подробности
    );
КонецФункции

Функция ПолучитьВеличинуКорабля(Поле, Посещённые, Строка, Колонка)
    КоличествоСтрок = Поле.Количество();
    КоличествоКолонок = Поле[0].Количество();
    КоличествоКлеток = 0;
    
    Очередь = Новый Массив();
    Очередь.Добавить(Новая Структура("Строка, Колонка", Строка, Колонка));
    
    Пока Очередь.Количество() > 0 Цикл
        Текущая = Очередь[0];
        Очередь.Удалить(0);
        
        Стр = Текущая.Строка;
        Кол = Текущая.Колонка;
        
        Если Стр < 0 ИЛИ Стр >= КоличествоСтрок 
            ИЛИ Кол < 0 ИЛИ Кол >= КоличествоКолонок 
            ИЛИ Посещённые[Стр][Кол] 
            ИЛИ Поле[Стр][Кол] = 0 Тогда
            Продолжить;
        КонецЕсли;
        
        Посещённые[Стр][Кол] = Истина;
        КоличествоКлеток = КоличествоКлеток + 1;
        
        Очередь.Добавить(Новая Структура("Строка, Колонка", Стр - 1, Кол));
        Очередь.Добавить(Новая Структура("Строка, Колонка", Стр + 1, Кол));
        Очередь.Добавить(Новая Структура("Строка, Колонка", Стр, Кол - 1));
        Очередь.Добавить(Новая Структура("Строка, Колонка", Стр, Кол + 1));
    КонецЦикла;
    
    Возврат КоличествоКлеток;
КонецФункции

Примеры использования

// Пример 1: базовое использование
Поле = Новый Массив();
Поле.Добавить(Новый Массив(0, 1, 0, 0, 0));
Поле.Добавить(Новый Массив(0, 1, 0, 1, 1));
Поле.Добавить(Новый Массив(0, 0, 0, 0, 0));
Поле.Добавить(Новый Массив(1, 1, 1, 0, 1));
Поле.Добавить(Новый Массив(0, 0, 0, 0, 1));

Значение = ПодсчитатьКораблиDFS(Поле);
Сообщить("Количество кораблей: " + Значение); // 4

// Пример 2: с подробностями
Результат = ПодсчитатьКораблиСДанными(Поле);
Сообщить("Всего кораблей: " + Результат.КоличествоКораблей);

ДляКаждого Корабль Из Результат.Подробности Цикл
    Сообщить("Корабль " + Корабль.Номер + ": размер " + Корабль.Размер);
КонецЦикла;

Анализ сложности

  • Временная сложность: O(m × n), где m и n — размеры поля. Каждая клетка посещается один раз.
  • Пространственная сложность: O(m × n) для матрицы посещённости + O(m × n) для стека/очереди в худшем случае.

Рекомендация

Для production-кода рекомендую реализацию 2 (BFS) — она итеративна, не требует глубокой рекурсии (без переполнения стека) и хорошо интегрируется с 1С.

Подсчёт кораблей в игре Морской бой | PrepBro