Перебор соседних клеток на двухмерном поле | Way23

Перебор соседних клеток на двухмерном поле

Рассмотрим задачу похожую на игру Сапёр

Дано прямоугольное поле размером n на m. В поле каждая клетка обозначена либо символом точки ('.') точкой либо звёздочки ('*'). Точка означает пустое поле поле, звёздочка мину. Вывести на экран поле такого же размера где вместо точек указанна цифра - количество мин рядом с этой клеткой.

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

Ограниченное поле

С клетками которые не находятся на границе поля проблем нет, можно просто последовательно перебрать все восемь вариантов field[y - 1][x - 1], field[y - 1][x] и тд. Но с клетками на границах такое не проходит - будет выход за границу списка. Первый вариант который приходит в голову добавить к каждому варианту условия:

if y > 0 and x > 0: if field[y - 1][x - 1] == '*': count += 1

if y > 0: if field[y - 1][x] == '*': count += 1

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

def countWithBorder(field, w, h, x, y): if field[y][x] == '*': return '*'

r = 0
for dx in range(-1, 2):
    for dy in range(-1, 2):
        if dx == 0 and dy == 0:
            continue

        curX = x + dx
        curY = y + dy

        if 0 <= curX < w and 0 <= curY < h:
            if field\[curY\]\[curX\] == '\*':
                r += 1
return str(r)

Неограниченное поле

Для неограниченного поля воспользуемся тем же способом, с применением оператора получения остаткаopen in new window. Для решения этой задачи знак остатка должен совпадать со знаком делителя, как в Python. Проверять через if в этом случае вообще ничего не придется, так как у любой клетки есть соседи.

def countWithoutBorder(field, w, h, x, y): if field[y][x] == '*': return '*'

r = 0
for dx in range(-1, 2):
    for dy in range(-1, 2):
        if dx == 0 and dy == 0:
            continue

        curX = (x + dx) % w
        curY = (y + dy) % h

        if field\[curY\]\[curX\] == '\*':
            r += 1
return str(r)

Полный код примера

w, h = [int(i) for i in input().split()]

field = [] for i in range(h): field.append(input())

def countWithBorder(field, w, h, x, y): if field[y][x] == '*': return '*'

r = 0
for dx in range(-1, 2):
    for dy in range(-1, 2):
        if dx == 0 and dy == 0:
            continue

        curX = x + dx
        curY = y + dy

        if 0 <= curX < w and 0 <= curY < h:
            if field\[curY\]\[curX\] == '\*':
                r += 1
return str(r)

def countWithoutBorder(field, w, h, x, y): if field[y][x] == '*': return '*'

r = 0
for dx in range(-1, 2):
    for dy in range(-1, 2):
        if dx == 0 and dy == 0:
            continue

        curX = (x + dx) % w
        curY = (y + dy) % h

        if field\[curY\]\[curX\] == '\*':
            r += 1
return str(r)

def printFiled(filed, h): for y in range(h): print(resultFiled[y])

print()

resultFiled = [] for y in range(h): resultFiled.append('') for x in range(w): resultFiled[y] = resultFiled[y] + countWithBorder(field, w, h, x, y) printFiled(resultFiled, h) print()

resultFiled = [] for y in range(h): resultFiled.append('') for x in range(w): resultFiled[y] = resultFiled[y] + countWithoutBorder(field, w, h, x, y) printFiled(resultFiled, h) print()

4 5 *... *... .*.. .... *...

*200 *310 2*10 2210 *100

*303 *312 2*11 2211 *202

Последниее изменение: 31.08.2021, 15:52:51