@GeloBer

Как оптимизировать алгоритм по выводу поля игры сапёр?

Всем хай! Написал код для решения следующей задачи.

Текст задачи:

Вам дан размер прямоугольного поля и координаты всех мин, расположенных на нём. Ваша задача составить карту этого поля. Клетки на карте должны быть заполнены одним из чисел: - -1, если в клетке лежит мина; - число от 0 до 8, которое показывает, сколько мин расположено в клетках, соседних с данной. Клетки считаются соседними, если у них есть общая вершина .

Формат входных данных
В первых двух строках вводятся два числа: количество строк N > 0 и количество столбцов M ≤ 100. В третьей строке вводится число K - количество мин, 0 ≤ K ≤ N* M. В последующих 2*K строках вводятся координаты мин, сначала номер строки, потом номер столбца. Нумерация строк и столбцов с 1. Гарантируется, что координаты мин не находятся вне поля, и никакие две мины не занимают одну клетку.

Формат выходных данных
Массив чисел размера N x M, состоящий из чисел от -1 до 8. Числа в строке массива разделяются пробелами. Каждая строка массива печатается с новой строки.

Примеры

Ввод
3
3
1
2
1
Вывод
1 1 0
-1 1 0
1 1 0

Ввод
4
2
2
4
2
4
1
Вывод
0 0
0 0
2 2
-1 -1

Мой код выглядит следующим образом:
def mine_search(i, j, m_array: list):
    count_mine = 0
    d = 0
    for m in range(len(m_array)):
        for c in range(2):
            if c == 0:
                d += (m_array[m][c] - i) ** 2
            else:
                d += (m_array[m][c] - j) ** 2
        if d == 2 or d == 1:
            count_mine += 1
        d = 0

    return count_mine


def sapper(array: list, m_array: list):
    for i in range(len(array)):
        for j in range(len(array[0])):
            array[i][j] = mine_search(i, j, m_array)
    for m in range(len(m_array)):
        for c in range(2):
            if c == 0:
                x = m_array[m][c]
            else:
                y = m_array[m][c]
        array[x][y] = -1
    return array


n = int(input())
m = int(input())
k = int(input())
m_array = [[int(input()) - 1 for c in range(2)] for k in range(k)]
array = [[0 for j in range(m)] for i in range(n)]
array = sapper(array, m_array)
for i in range(len(array)):
    print(*array[i])


В общем, задача решена верна, однако она не может пройти некоторые тесты из-за превышения допустимого времени в одну секунду. Прошу помочь оптимизировать мой код и указать на мои ошибки. Заранее спасибо!))
  • Вопрос задан
  • 154 просмотра
Решения вопроса 1
hint000
@hint000
у админа три руки
Выкинуть mine_search(...) в мусор целиком.
sapper(...) переписать следующим образом: сначала проходим циклом по m_array и расставляем в array мины.
Только после полной расстановки мин заполняем нулевые клетки. Это очень сильно ускорит выполнение.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы