Не могу найти ошибку в коде. Задача с сайта ACMP (951 вирус)

Question

На вход дают размены матрицы N, M (количество строк и столбцов соответственно). На 2 строчке число K - клеток с вирусами и сами клетки вирусов. Через каждую единицу времению происходит заражение ближайших клеток. Нужно вывести время заражения всей области.

Пример:
Ввод 4 5 
2 2 1 4 5 
Вывод 4

Мой код на 10 тесте выдает неправильный ответ

def f(e):
    gg=[]
    for i in range(n):
        for j in range(m):
            if e[i][j]==1:
                if (j+1)<m:
                    gg.append(i)
                    gg.append(j+1)
                if (j-1)>=0:
                    gg.append(i)
                    gg.append(j-1)
                if(i-1)>=0:
                    gg.append(i-1)
                    gg.append(j)
                if (i+1)<n:
                    gg.append(i+1)
                    gg.append(j)
    for i in range(0,len(gg),2):
        e[gg[i]][gg[i+1]]=1
        
    return e


gg=[]
n,m=map(int,input().split())
mas=[]
ss=0
fff=0
t=0
d=list(map(int,input().split()))
r=1
for i in range(n):
    ff=[]
    for j in range(m):
        if r<len(d):
            if (i+1)==d[r] and (j+1)==d[r+1]:
                ff.append(1)
                r+=2
            else:
                ff.append(0)
        else:
            ff.append(0)
    mas.append(ff)
    #print(mas)
for i in range(n):
    ss+=sum(mas[i])
if ss==n*m:
    print(0)
else:
    for i in range(80):
        mas=f(mas)
        ss=0
        t=t+1
        if fff:
            break
        ###print(t)
        for i in range(n):
            ss+=sum(mas[i])
            ###print(mas[i])
            if ss==m*n:
                print(t)
                fff=1
                break

Answer 1

Как минимум, у вас ошибка в алгоритме инициализации. Вы ожидаете на входе отсортированные координаты. Например, попробуйте переставить пары координат (2 1 и 4 5) из вашего примера входных данных, и увидите, что начальное состояние вашей матрицы будет неправильное.
Вот такой ввод:

4 5 
2 4 5 2 1

Ну и вообще, программу можно составить более компактно.

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

x, *coords = map(int, input().split())
for i in range(x):
    matrix[coords[i*2+1]-1][coords[i*2]-1] = True

count = 0
while not all(sum(matrix, [])):
    new_matrix = [matrix[i].copy() for i in range(m)]
    for col in range(n):
        for row in range(m):
            if matrix[row][col]:
                for dc, dr in ((-1,0), (0,-1), (1,0), (0,1)):
                    c, r = col + dc, row + dr
                    if 0 <= c < n and 0 <= r < m:
                        new_matrix[r][c] = True
    count += 1
    matrix = new_matrix

print(count)

БЛОГ НА HUSL

Не могу найти ошибку в коде. Задача с сайта ACMP (951 вирус)

Ответы (1 шт):