Морской бой — разбор задачи

1. Идея

Нужно обработать много выстрелов по полю n × n и для каждого быстро определить результат:

• miss, если стреляем в пустую клетку или повторно в уже обстрелянную;
• hit, если попали в корабль, но он ещё не уничтожен;
• sunk, если этим выстрелом добили корабль.

Главная трудность — понять, к какому кораблю относится каждая клетка '#', и сколько у этого корабля осталось неповреждённых клеток.

Для этого заранее разобьём все клетки кораблей на компоненты связности по сторонам. Каждая такая компонента — это один корабль. После этого:

• для каждой клетки будем знать id корабля;
• для каждого корабля будем хранить число ещё не подбитых клеток.

Тогда каждый запрос обрабатывается за O(1).

2. Наблюдения

Наблюдение 1

По условию корабль — это связная по стороне полоска клеток, а разные корабли не касаются даже по углу.

Значит, если смотреть только на соседей сверху, снизу, слева и справа, то каждая связная компонента из символов '#' — это ровно один корабль.

Наблюдение 2

Не нужно каждый раз заново искать весь корабль после выстрела. Достаточно один раз до начала запросов:

• найти все корабли;
• посчитать их размеры.

Тогда при попадании в клетку корабля мы просто уменьшаем число живых клеток этого корабля на 1.

Наблюдение 3

Повторный выстрел по той же клетке всегда даёт miss, независимо от того, что там было раньше.

Значит, нужно хранить отдельную таблицу shot, где отмечено, стреляли ли уже в клетку.

Наблюдение 4

Размер поля до 1000 × 1000, то есть до 10^6 клеток. Это позволяет один раз сделать обход всей сетки в ширину и обработать все клетки.

Количество выстрелов до 10^5, поэтому на каждый запрос нужен очень быстрый ответ.

3. Алгоритм

Предобработка поля

Создадим:

• ship_id[r][c] — номер корабля для клетки (r, c), либо -1, если это не корабль;
• alive[id] — сколько целых клеток осталось у корабля с номером id.

Дальше пройдём по всем клеткам поля:

• если клетка пустая '.', пропускаем;
• если это '#', но она ещё не размечена, значит найден новый корабль;
• запускаем BFS из этой клетки;
• все найденные в BFS клетки получают один и тот же id;
• одновременно считаем размер компоненты;
• после завершения BFS записываем этот размер в alive.

Обработка запросов

Для каждой команды (r, c):

1. Переведём координаты к индексации с нуля.
2. Если в клетку уже стреляли, выводим miss.
3. Иначе помечаем клетку как обстрелянную.
4. Если в этой клетке '.', выводим miss.
5. Иначе это клетка корабля:
   • находим id = ship_id[r][c];
   • уменьшаем alive[id] на 1;
   • если alive[id] == 0, выводим sunk;
   • иначе выводим hit.

4. Почему это работает

Докажем корректность решения.

1. BFS правильно находит корабли

Мы запускаем обход в ширину только из клеток '#' и переходим только по четырём направлениям.

По условию каждый корабль состоит из клеток, связанных по стороне. Значит, все клетки одного корабля будут найдены одним BFS.

Так как разные корабли не соприкасаются по стороне, BFS не сможет перейти с одного корабля на другой.

Следовательно, каждая найденная компонента связности — это ровно один корабль.

2. ship_id правильно определяет принадлежность клетки кораблю

После предобработки каждая клетка '#' получила номер компоненты, в которой она находится. Поскольку каждая компонента — это ровно один корабль, ship_id[r][c] действительно хранит номер корабля для этой клетки.

3. alive[id] всегда равно числу ещё не подбитых клеток корабля

Изначально alive[id] равно размеру корабля, то есть числу всех его клеток.

Дальше при каждом первом попадании в клетку этого корабля мы уменьшаем alive[id] на 1.

Повторный выстрел в ту же клетку не уменьшает значение, потому что сразу даёт miss.

Значит, в любой момент alive[id] точно равно количеству ещё не подбитых клеток корабля.

4. Ответ на запрос определяется верно

Для запроса возможны три случая:

• если в клетку уже стреляли, по условию ответ miss;
• если клетка пустая, ответ miss;
• если это новая неповреждённая клетка корабля, то после уменьшения alive[id]:
  • если осталось 0, корабль уничтожен, значит sunk;
  • иначе у корабля ещё есть целые клетки, значит hit.

Все варианты обработаны правильно, значит алгоритм корректен.

5. Сложность

Пусть всего на поле n^2 клеток.

Предобработка

Каждая клетка посещается не более одного раза в BFS.

Поэтому время: O(n^2)

Обработка выстрелов

Каждый запрос обрабатывается за O(1).

Для q запросов время: O(q)

Итого

Общая сложность: O(n^2 + q)

Память

Храним:

• поле;
• массив ship_id;
• массив shot;
• размеры кораблей.

Итого память: O(n^2)

6. Код на C++17

#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<string> grid(n);
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }

    vector<vector<int>> ship_id(n, vector<int>(n, -1));
    vector<int> alive;
    int current_id = 0;

    int dr[4] = {-1, 1, 0, 0};
    int dc[4] = {0, 0, -1, 1};

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] != '#' || ship_id[i][j] != -1) {
                continue;
            }

            queue<pair<int, int>> q;
            q.push({i, j});
            ship_id[i][j] = current_id;
            int size = 0;

            while (!q.empty()) {
                pair<int, int> v = q.front();
                q.pop();
                int r = v.first;
                int c = v.second;
                size++;

                for (int k = 0; k < 4; k++) {
                    int nr = r + dr[k];
                    int nc = c + dc[k];
                    if (nr < 0 || nr >= n || nc < 0 || nc >= n) {
                        continue;
                    }
                    if (grid[nr][nc] != '#') {
                        continue;
                    }
                    if (ship_id[nr][nc] != -1) {
                        continue;
                    }
                    ship_id[nr][nc] = current_id;
                    q.push({nr, nc});
                }
            }

            alive.push_back(size);
            current_id++;
        }
    }

    vector<vector<bool>> shot(n, vector<bool>(n, false));

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int r, c;
        cin >> r >> c;
        r--;
        c--;

        if (shot[r][c]) {
            cout << "miss\n";
            continue;
        }

        shot[r][c] = true;

        if (grid[r][c] == '.') {
            cout << "miss\n";
            continue;
        }

        int id = ship_id[r][c];
        alive[id]--;

        if (alive[id] == 0) {
            cout << "sunk\n";
        } else {
            cout << "hit\n";
        }
    }

    return 0;
}

7. Код на Python 3

from collections import deque

n = int(input())
grid = [input().strip() for _ in range(n)]

ship_id = [[-1] * n for _ in range(n)]
alive = []
current_id = 0

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

for i in range(n):
    for j in range(n):
        if grid[i][j] != '#' or ship_id[i][j] != -1:
            continue

        q = deque()
        q.append((i, j))
        ship_id[i][j] = current_id
        size = 0

        while q:
            r, c = q.popleft()
            size += 1

            for k in range(4):
                nr = r + dr[k]
                nc = c + dc[k]
                if nr < 0 or nr >= n or nc < 0 or nc >= n:
                    continue
                if grid[nr][nc] != '#':
                    continue
                if ship_id[nr][nc] != -1:
                    continue
                ship_id[nr][nc] = current_id
                q.append((nr, nc))

        alive.append(size)
        current_id += 1

shot = [[False] * n for _ in range(n)]

q = int(input())
for _ in range(q):
    r, c = map(int, input().split())
    r -= 1
    c -= 1

    if shot[r][c]:
        print("miss")
        continue

    shot[r][c] = True

    if grid[r][c] == '.':
        print("miss")
        continue

    sid = ship_id[r][c]
    alive[sid] -= 1

    if alive[sid] == 0:
        print("sunk")
    else:
        print("hit")