Проблема гниения апельсина - невозможно получить ожидаемое значение

Question

Итак, задача состоит из корзины из n строк и m столбцов, найдите минимальное количество дней, необходимое для гниения всех апельсинов, зная, что всегда есть как минимум 1 гнилой оранжевый в корзине, и их позиции указаны как входной вложенный список позиции .

(РЕДАКТИРОВАТЬ: извинения, забыл добавить правило гниения, но в основном соседние апельсины с гнилым апельсином должны гнить на следующий день, например, если апельсин в [1,1] гнил сегодня, апельсины в [0,1], [2,1], [1,0], [1,2] должны гнить на следующий день)

Просто не могу получить ожидаемый результат из ввода ниже, и я не вижу, где мой код пошел не так. На самом деле начинает казаться, что ожидаемый результат как-то проблематичен c. Было бы здорово получить несколько советов.

Ввод : n = 3, m = 7, position = [[2,4]]

Ожидаемый результат : 4

Фактический выход : 6

def rottingOrange(n,m,positions):
    #Idea: Find cells that have not rotten
    #If either cell next to it have rotten, it will also rot
    #If there is no more cells that have not rot, stops
    
    def isValid(i,j,positions):
        #Determine if an orange position is adjacent to a rotten orange
        if [i-1,j] in positions or [i+1,j] in positions or [i,j-1] in positions or [i,j+1] in positions:
            return True
        else:
            return False

    def rot(grid,positions):
        #Find all oranges that should rot for the current day
        temp = []
        for i,j in grid:
            if isValid(i,j,positions): 
                temp = temp + [[i,j]]
        if len(temp) < 1:
            return "cannot rot"
        else:
            grid_new = [x for x in grid if x not in temp]
            positions_new = positions + temp
            return grid_new, positions_new

    def rotting(grid, positions):
        #find the number of days taken to rot all oranges
        if len(grid) <= 0 or rot(grid, positions) == "cannot rot":
            return 0
        else:
            grid_new = rot(grid,positions)[0]
            positions_new = rot(grid,positions)[1]
            if len(grid_new) == len(grid):
                return rotting(grid_new,positions_new)
            else:
                return 1 + rotting(grid_new,positions_new)

    def grid_creation(n,m,positions):
        #create grid of size n x m, and remove all oranges that have rotten
        grid = []
        for i in range(n):
            for j in range(m):
                grid.append([i,j])
        for x in positions:
            if x in grid:
                grid.remove(x)
        return grid

    if __name__ == "__main__":
        grid = grid_creation(n,m,positions)
        return rotting(grid,positions)

Answer 1

Ваша программа основана на index. Если Position [[2,4]], то позиция индекса - [[1, 3]]. Вы получите ожидаемый результат как 4, если вы предоставите позицию индекса в качестве ввода или вы можете скрыть позицию в позиции индекса внутри своей программы.

Также найдите другой подход к проблеме.

def get_neb_pos_list(r_lim, c_lim, r_pos):
        neb_list = [(r_pos[0] + 1, r_pos[1]) if r_pos[0] + 1 < r_lim else (r_pos[0], r_pos[1])] + \
                   [(r_pos[0] - 1, r_pos[1]) if r_pos[0] - 1 >= 0 else (r_pos[0], r_pos[1])] + \
                   [(r_pos[0], r_pos[1] + 1) if r_pos[1] + 1 < c_lim else (r_pos[0], r_pos[1])] + \
                   [(r_pos[0], r_pos[1] - 1) if r_pos[1] - 1 >= 0 else (r_pos[0], r_pos[1])]
   return neb_list


def get_min_days_to_rot(n_rows, n_cols, r_pos):
    oranges = [(i, j) for i in range(n_rows) for j in range(n_cols)]
    if r_pos[0] not in oranges:
        return "Invalid Position"
    if n_rows <= 0 or n_cols <= 0:
        return "Invalid number of rows or columns"
    if len(oranges) == 1:
        return 0
    rot_oranges = list(r_pos)
    n_days = 0
    while len(rot_oranges) < n_rows * n_cols:
        for pos in r_pos:
            rot_list = get_neb_pos_list(n_rows, n_cols, pos)
            rot_oranges.extend(rot_list)
        rot_oranges = list(set(rot_oranges))
        r_pos = list(rot_oranges)
        n_days += 1
    return n_days


if __name__ == "__main__":
    n = 3
    m = 7
    pos = [(1,3)]
    n_days = get_min_days_to_rot(n, m, pos)
    print(n_days)