@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])


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

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

Войти через центр авторизации
Похожие вопросы