How to optimize the algorithm for deriving the field of play of the sapper?

Question

Python

Hi all! Wrote code to solve the following problem.

Problem text:

You are given the size of a rectangular field and the coordinates of all the mines located on it. Your task is to map this field. Cells on the map must be filled with one of the following numbers: - -1 if there is a mine in the cell; - a number from 0 to 8, which shows how many mines are located in the cells adjacent to this one. Cells are considered adjacent if they have a common vertex.

Input data format
The first two lines contain two numbers: the number of rows N > 0 and the number of columns M ≤ 100. The third line contains the number K - the number of min, 0 ≤ K ≤ N* M. The next 2*K lines contain the coordinates of the min, first the number row, then the column number. Numbering of rows and columns starts from 1. It is guaranteed that the coordinates of the mines are not outside the field, and no two mines occupy the same cell.

Output data format
An array of numbers of size N x M, consisting of numbers from -1 to 8. The numbers in the array line are separated by spaces. Each line of the array is printed on a new line.

Examples

Input
3
3
1
2
1
Output
1 1 0
-1 1 0
1 1 0

Input
4
2
2
4
2
4
1
Output
0 0
0 0
2 2
-1 -1

My code looks like this:

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

In general, the problem is solved correctly, however, it fails some tests due to exceeding the allowable time of one second. Please help me optimize my code and point out my mistakes. Thanks in advance!))

Answer 1

Throw mine_search(...) into the trash entirely.
rewrite sapper(...) as follows: first, loop through m_array and place mines in the array.
Only after the full placement of the mines, we fill in the zero cells. This will greatly speed up the execution.