Клетчатое поле и координаты

Начинается модуль про графы и динамику, и оба этих больших приёма чаще всего живут на клетчатом поле. Поэтому сначала научимся уверенно обращаться с самим полем.

Поле — это список списков, с которым мы уже работали. Новое здесь одно: клетка задаётся парой (строка, столбец), и почти все ошибки темы растут из путаницы в этой паре.

n, m = map(int, input().split())
grid = [input() for _ in range(n)]     # поле из символов

grid[r][c]        # сначала строка, потом столбец

Две системы нумерации

В условии клетки почти всегда нумеруются с единицы. В списке — с нуля. Держать в голове обе одновременно невозможно, поэтому есть простое правило:

Вычитайте единицу сразу при чтении и дальше думайте только в списочных номерах. Прибавляйте её обратно только при выводе.

r, c = map(int, input().split())
r -= 1
c -= 1
# дальше в программе r и c — настоящие индексы

Смешивать два счёта в одной программе — верный способ получить ответ, отличающийся ровно на единицу, и потом долго искать где.

Строка и столбец — не одно и то же

У поля $n \times m$ строк $n$, а столбцов $m$. Значит r меняется от 0 до $n-1$, а c — от 0 до $m-1$. На квадратном поле перепутать их безнаказанно, на прямоугольном — программа упадёт или, что хуже, не упадёт.

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

Правильный способ — список смещений:

DIRS = ((-1, 0), (1, 0), (0, -1), (0, 1))          # четыре стороны

for dr, dc in DIRS:
    nr = r + dr
    nc = c + dc
    if 0 <= nr < n and 0 <= nc < m:
        ...    # сосед существует, можно смотреть grid[nr][nc]

Восемь направлений — тот же список из восьми пар. Меняется одна строчка, а не весь цикл.

Проверять границы надо ДО обращения

Это главное правило темы, и в Python оно особенно важно.

В большинстве языков выход за границу массива приводит к аварии — программа падает, и вы сразу знаете, что не так. В Python отрицательный индекс не ошибка. Запись grid[-1] вернёт последнюю строку, grid[0][-1] — последний символ первой строки.

grid = ["ab", "cd"]
grid[-1][0]     # "c" — не авария, а последняя строка!

Из-за этого забытая проверка nr >= 0 не роняет программу, а тихо подставляет клетку с противоположного края поля. Ответ получается неправильным, тесты падают, а место ошибки ничем себя не выдаёт.

Поэтому условие пишется целиком: 0 <= nr < n and 0 <= nc < m. Двойное сравнение в Python работает именно так, как читается, и обе границы проверяются сразу.

Поле хранится в списке grid из $n$ строк. Программа обращается к grid[nr][nc], где nr оказалось равным −1.

Что произойдёт?

Типичная задача: робот стоит на поле и получает строку команд U, D, L, R.

Главное здесь — понять, что поле хранить не нужно. У робота есть только пара чисел, и команда меняет одну из них:

for command in commands:
    if command == "U" and row > 0:
        row -= 1
    elif command == "D" and row < n - 1:
        row += 1
    ...

Это позволяет решать задачи с полем в миллиард клеток: памяти уходит на две переменные.

Что делать с краем

Условие всегда описывает одно из трёх поведений, и их надо различать:

Последний случай — «поле-бублик» — решается остатком. Осторожно с движением назад: (row - 1) % n в Python даёт правильный результат даже при row = 0, потому что остаток здесь неотрицательный. В C++ пришлось бы писать (row - 1 + n) % n.

Это тот редкий случай, когда питоновское поведение остатка работает в нашу пользу — но привычку прибавлять $n$ лучше сохранить: она не мешает и переносится на другие языки.

Поле 5 × 5. Сколько соседей у угловой клетки, если соседними считаются клетки по стороне и по диагонали?

Введите целое число.

Кроме соседей, у поля есть направления, вдоль которых удобно ходить целиком.

Строка и столбец. Строка — это grid[r] целиком. Столбец приходится собирать: [grid[r][c] for r in range(n)]. Несимметричность списка списков — то, к чему надо привыкнуть.

Диагонали. На главной диагонали номера строки и столбца равны: grid[i][i]. На побочной их сумма постоянна: grid[i][n - 1 - i].

Более общее наблюдение, которое пригодится дальше: у всех клеток одной побочной диагонали одинакова сумма r + c, а у клеток одной главной — разность r - c. Это превращает диагональ в обычный номер:

sums = [0] * (n + m - 1)
for r in range(n):
    for c in range(m):
        sums[r + c] += grid[r][c]      # номер диагонали — это r + c

Накопленные суммы на плоскости

Приём из занятия про префиксные суммы работает и здесь. Заведём таблицу, где в ячейке $(r, c)$ лежит сумма всего прямоугольника от левого верхнего угла до этой клетки:

prefix[r][c] = prefix[r-1][c] + prefix[r][c-1] - prefix[r-1][c-1] + grid[r-1][c-1]

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

Перепутаны строка и столбец. На квадратном поле проходит, на прямоугольном — падает. Проверяйте решение на поле 1 × 5 и 5 × 1: они ловят это мгновенно.

Забытая проверка на отрицательный индекс. Разобрана выше. Программа не падает, а тихо берёт клетку с другого края. Самая коварная ошибка темы.

Проверка границ после обращения. if grid[nr][nc] == "*" and 0 <= nr < n — обращение уже произошло. Условие проверяется слева направо, и порядок здесь принципиален.

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

Строка поля прочитана вместе с переводом строки. Если читать через sys.stdin, в конце строки останется невидимый символ, и длина окажется на единицу больше. Отрезайте его сразу.

Как проверять себя

• поле 1 × 1 — у клетки нет соседей вовсе;
• поле 1 × m и n × 1 — ловят путаницу строк со столбцами;
• клетка в углу и на краю — там и срабатывают забытые проверки;
• прямоугольное поле, а не квадратное — квадрат прощает слишком многое.

Лестница прежняя: пять разминочных, семь основных, три со звёздочкой. Зачёт при десяти решённых.

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

В части задач поле огромно — до миллиарда клеток. Это подсказка: хранить его не надо, нужны только координаты.

Задача: «дано поле из точек и звёздочек; посчитайте, сколько пар звёздочек стоят в соседних по стороне клетках».

Ученик написал:

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

count = 0
for r in range(n):
    for c in range(m):
        if grid[r][c] != "*":
            continue
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nr = r + dr
            nc = c + dc
            if nr < n and nc < m:
                if grid[nr][nc] == "*":
                    count += 1

print(count // 2)

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

Постройте вход, на котором она ошибается, объясните, почему ошибка не проявляется как авария, и предложите исправление.