← Сtrl

izekia · Ноя. 14, 2016 17:21:49

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

izekia · Ноя. 14, 2016 17:33:21

в общем если на скорость, то по-другому надо делать, а на втором сайте места под стек не хватает

FishHook · Ноя. 14, 2016 17:46:00

проверяйте

 def fn(data):
    #Prepare data
    n = m = None
    matrix = []
    metric, field = data.split("\n", 1)
    n, m = map(int, metric.split())
    for row in field.split("\n"):
        matrix.append([x == "#" for x in row])
    beds = 0
    mapping = {}
    for row_num, row in enumerate(matrix):
        for col_num, cell in enumerate(row):
            if not cell:
                continue
            neighbors = []
            if row_num > 0:
                if matrix[row_num-1][col_num]:
                    neighbors.append((row_num-1, col_num))
            if col_num < m - 1:
                if matrix[row_num][col_num + 1]:
                    neighbors.append((row_num - 1, col_num))
            if row_num < n - 1:
                if matrix[row_num + 1][col_num]:
                    neighbors.append((row_num + 1, col_num))
            if col_num > 0:
                if matrix[row_num][col_num - 1]:
                    neighbors.append((row_num, col_num - 1))
            if not neighbors:
                beds += 1
                continue
            for neighbor in neighbors:
                if neighbor in mapping:
                    bed_num = mapping[neighbor]
                    mapping[(row_num, col_num)] = bed_num
                    break
            else:
                beds += 1
                mapping[(row_num, col_num)] = beds
    return beds
data = """5 10
##......#.
.#..#...#.
.###....#.
..##....#.
........#."""
print fn(data)

Отредактировано FishHook (Ноя. 14, 2016 17:46:48)

valoroso · Ноя. 14, 2016 22:52:40

FishHook
проверяйте

data = """5 10
##..#####.
.#.#.#....
###..##.#.
..##.....#
.###.#####"""

уже ошибка, 8 вместо 5.
а так алгоритм шустрый.

Отредактировано valoroso (Ноя. 14, 2016 22:58:06)

valoroso · Ноя. 14, 2016 23:02:43

izekia
valorosoда я знаю, сразу бы сказал … я в свое время и так потратил много на сферу, кстати, лучше там тренируйся, там хотя бы причину ошибки можно увидеть

я обычно на codewars и то C#. А тут кровь из носа надо эту задачу именно на Питоне решить. Хотя разнообразие всегда хорошо)

izekia · Ноя. 14, 2016 23:05:13

valoroso
я обычно на codewars и то C#. А тут кровь из носа надо эту задачу именно на Питоне решить. Хотя разнообразие всегда хорошо)

ну если до завтра ждет то я сделаю

valoroso · Ноя. 14, 2016 23:11:55

izekia

янтарь или виски?)

izekia · Ноя. 15, 2016 00:01:03

все еще неоптимально, но быстрее

 def solve1(N, M, case):
    l = [[0] * M for i in range(N)]
    n = 0
    connected = set()
    for i in range(N):
        for j in range(M):
            x = 0
            if case[i][j] == '#': 
                if (i > 0 and l[i-1][j] != 0):
                    x = l[i-1][j]
                left = l[i][j-1]
                if (j > 0 and left != 0):
                    if x != left:
                        if x > 0:
                            connected.add(frozenset((x, left)))
                        else:
                            x = left
                if x == 0:
                    n += 1
                    x = n
                l[i][j] = x
    #print('\n'.join(str(r) for r in case))
    #print('\n'.join(str(r) for r in l))
    #print(connected)
    return n - len(connected)

Отредактировано izekia (Ноя. 15, 2016 00:18:51)

FishHook · Ноя. 15, 2016 05:32:33

Ага! А вот такой вариант попробуйте

 def fn(data):
    matrix = []
    metric, field = data.split("\n", 1)
    n, m = map(int, metric.split())
    for row in field.split("\n"):
        matrix.append([x == "#" for x in row])
    beds = 0
    mapping = {}
    for row_num, row in enumerate(matrix):
        for col_num, cell in enumerate(row):
            if not cell:
                continue
            neighbors = []
            if row_num > 0:
                if matrix[row_num - 1][col_num]:
                    neighbors.append((row_num - 1, col_num))
            if col_num < m - 1:
                if matrix[row_num][col_num + 1]:
                    neighbors.append((row_num, col_num + 1))
            if row_num < n - 1:
                if matrix[row_num + 1][col_num]:
                    neighbors.append((row_num + 1, col_num))
            if col_num > 0:
                if matrix[row_num][col_num - 1]:
                    neighbors.append((row_num, col_num - 1))
            if not neighbors:
                beds += 1
                mapping[(row_num, col_num)] = beds
                continue
            for neighbor in neighbors:
                if neighbor in mapping:
                    bed_num = mapping[neighbor]
                    break
            else:
                beds += 1
                bed_num = beds
            mapping[(row_num, col_num)] = bed_num
            redraw = None
            for neighbor in neighbors:
                if neighbor in mapping and mapping[neighbor] != bed_num:
                    redraw = mapping[neighbor]
                mapping[neighbor] = bed_num
            if redraw:
                for el in mapping:
                    if mapping[el] == bed_num:
                        mapping[el] = redraw
    return len(set(mapping.values()))
data = """5 10
##..#####.
.#.#.#....
###..##.#.
..##.....#
.###.#####"""
print fn(data)

valoroso · Ноя. 15, 2016 09:29:32

izekia
все еще неоптимально, но быстрее

Python-сообщество

Уведомления

#1 Ноя. 14, 2016 17:21:49

Обход в глубину

#2 Ноя. 14, 2016 17:33:21

Обход в глубину

#3 Ноя. 14, 2016 17:46:00

Обход в глубину

#4 Ноя. 14, 2016 22:52:40

Обход в глубину

#5 Ноя. 14, 2016 23:02:43

Обход в глубину

#6 Ноя. 14, 2016 23:05:13

Обход в глубину

#7 Ноя. 14, 2016 23:11:55

Обход в глубину

#8 Ноя. 15, 2016 00:01:03

Обход в глубину

#9 Ноя. 15, 2016 05:32:33

Обход в глубину

#10 Ноя. 15, 2016 09:29:32

Обход в глубину

Board footer