1. Идея

Нужно обработать каждую клетку поля:

• если там стоит мина '*', то в ответе тоже будет '*';
• если там безопасная клетка '.', надо посчитать, сколько мин находится среди её соседей.

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

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

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

2. Удобно заранее записать все 8 смещений:

   • (-1, -1), (-1, 0), (-1, 1)
   • (0, -1), (0, 1)
   • (1, -1), (1, 0), (1, 1)

3. Ответ удобно хранить в отдельной таблице ans. Тогда:

   • мины просто копируются как '*';
   • для остальных клеток записывается символ цифры от '0' до '8'.

4. Ограничения до 1000 x 1000 позволяют пройти по всем клеткам и для каждой проверить 8 соседей. Это будет достаточно быстро.

3. Алгоритм

1. Считать n и m.
2. Считать поле в массив строк field.
3. Создать таблицу ответа ans размера n x m, сначала заполненную символами '0'.
4. Завести два массива смещений для 8 направлений:
   • dr — изменение строки,
   • dc — изменение столбца.
5. Для каждой клетки (r, c):
   • если field[r][c] == '*', то ans[r][c] = '*';
   • иначе:
     1. положить cnt = 0;
     2. перебрать все 8 направлений;
     3. вычислить соседа (nr, nc);
     4. если сосед внутри поля и там мина, увеличить cnt;
     5. записать в ans[r][c] цифру cnt.
6. Вывести все строки таблицы ans.

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

Рассмотрим любую клетку поля.

Случай 1: в клетке мина

По условию символ '*' должен остаться без изменений. Алгоритм именно так и делает: сразу записывает '*' в ответ.

Случай 2: клетка безопасная

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

Алгоритм перебирает все эти 8 направлений. Для каждого направления:

• вычисляет координаты соседней клетки;
• проверяет, что они не выходят за границы поля;
• если сосед существует и в нём мина, увеличивает счётчик.

Таким образом, счётчик cnt после перебора равен точному количеству соседних мин. Именно это число и записывается в ответ.

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

5. Сложность

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

Для каждой клетки мы проверяем не более 8 соседей, то есть делаем константное число операций.

• Временная сложность: O(n * m)
• Дополнительная память: O(n * m) для массива ответа

6. Код на C++17

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

using namespace std;

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

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

    vector<string> ans(n, string(m, '0'));

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

    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            if (field[r][c] == '*') {
                ans[r][c] = '*';
            } else {
                int cnt = 0;
                for (int k = 0; k < 8; k++) {
                    int nr = r + dr[k];
                    int nc = c + dc[k];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < m && field[nr][nc] == '*') {
                        cnt++;
                    }
                }
                ans[r][c] = char('0' + cnt);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

7. Код на Python 3

n, m = map(int, input().split())
field = [input() for _ in range(n)]

ans = [['0'] * m for _ in range(n)]

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

for r in range(n):
    for c in range(m):
        if field[r][c] == '*':
            ans[r][c] = '*'
        else:
            cnt = 0
            for k in range(8):
                nr = r + dr[k]
                nc = c + dc[k]
                if 0 <= nr < n and 0 <= nc < m and field[nr][nc] == '*':
                    cnt += 1
            ans[r][c] = str(cnt)

for i in range(n):
    print(''.join(ans[i]))