Flood-Fill Slow Execution - PullRequest
Новая
       37

Flood-Fill Slow Execution

0 голосов
/ 10 февраля 2019

С учетом ввода: 

arr = [["###########...."]
       ["#.......c.###.."]
       ["####......#.#.."]
       [".#.########.#.."]
       ["##...#..b#..#.."]
       ["#.a.#...#...###"]
       ["####.#.#d###..#"]
       ["......#...e#xx#"]
       [".#....#########"]
       [".#.x..#..#....."]
       [".######.c#....."]
       ["......####....."]]

Обратите внимание, что # - это экстент, в котором могут перемещаться слова (a, b, c, d и т. Д.), Тогда как . обозначает действительный ход.Я пытаюсь выяснить, есть ли в области, где живет слово, другое слово сущности.

Я подумал, что алгоритм заливки будет идеальным решением для этой проблемы, когда я могу обнаружить другую сущность во время прохождения области,поэтому я попытался сделать: 

import collections

def patrol(grid, row, col, R, C, army, visited):
    danger = False
    visited.append([row, col]) 
    row_change = [-1, 0, 1, 0]
    col_change = [0, 1, 0, -1]

    for direction in range(4):

        new_row = row + row_change[direction]
        new_col = col + col_change[direction]
        if (new_row < 0) or (new_row >=  R) or (new_col < 0) or (new_col >= C) or (grid[new_row][new_col] == "#") :
            continue
        else:
            if ((grid[new_row][new_col] == ".") or (grid[new_row][new_col] == army)):
                if ([new_row, new_col] not in visited):
                    visited.append([new_row, new_col])
                    if(patrol(grid, new_row, new_col, R, C, army, visited)):
                        danger = True
                        return danger
                else:
                    continue
            else:
                danger = True
                return danger

    return danger

И моя основная функция: 

def main():
        #THIS IS THE INPUT
        really_raw_input = [2, 2, 2, ".#", "#a", 12, 15, '###########....', '#.......c.###..', '####......#.#..', '.#.########.#..', '##...#..b#..#..', '#.a.#...#...###', '####.#.#d###..#', '......#...e#xx#', '.#....#########', '.#.x..#..#.....', '.######.c#.....', '......####.....']
        number_of_game = int(really_raw_input.pop(0))

        results = []

        for _ in range(number_of_game):

            R = int(really_raw_input.pop(0))
            C = int(really_raw_input.pop(0))

            grid = []
            armies_coordinate = {}

            for row in range(R):
                grid.append(really_raw_input.pop(0))

                for character in set(grid[-1]):
                    if (character == "#") or (character == "."):
                        continue
                    else:
                        if character in armies_coordinate:
                            armies_coordinate[character].append([row, grid[-1].index(character)])
                        else:
                            armies_coordinate[character] = [[row, grid[-1].index(character)]]

            temp = armies_coordinate
            for army, coordinates in temp.items():
                    for coordinate in coordinates:
                        if (patrol(grid, coordinate[0], coordinate[1], R, C, army, [])):

    armies_coordinate[army].pop(armies_coordinate[army].index(coordinate))
    results.append(collections.OrderedDict(sorted(armies_coordinate.items())))

        return results

Наконец я запустил: 

result = main()
contested = 0
iteration = 1

for coordinates in result:
    print("Case {}".format(iteration))
    for key, value in coordinates.items():
        if len(value) != 0:
            print("{} {}".format(key, len(value)))
        else:
            contested += 1

    print("Contested {}".format(int(contested/2)))

    iteration += 1

Он успешно возвращает результаты для 2 случаев. Но как только я введу больший ввод , скажем, 100 дел с 100 строками и столбцами, для завершения потребовалось около 6 минут.Это довольно долго для моего требования.

Что я могу сделать, чтобы сделать это быстрее?

...