DjangoBB LoFi version

Полная версия: Помогите с решением задачи

Начало » Центр помощи » Помогите с решением задачи

EvilRoot

Окт. 9, 2016 17:56:56

Добрый день!
Я получил задачу для реализации на Python.

Предположим, в один прекрасный день вы оказались на острове прямоугольный формы.
Ландшафт этого острова можно описать с помощью целочисленной матрицы размером MxN, каждый элемент которой задаёт высоту соответствующей области острова над уровнем моря.

К примеру, вот небольшой остров размером 3x3:
4 5 4
3 1 5
5 4 1

В сезон дождей остров полностью заливает водой и в низинах скапливается вода. Низиной будем считать такую область острова, клетки которой граничат с клетками, большими по высоте. При этом диагональные соседи не учитываются, а уровень моря принимается за 0. В приведённом выше примере на острове есть только одна низина — это клетка со значением 1 в середине острова (она граничит с клетками высотой 3, 5, 5 и 4).

Таким образом, после дождя высота клеток острова изменится и станет следующей:
4 5 4
3 3 5
5 4 1

Мы видим что в данном примере высота низины изменилась с 1 до 3, после чего вода начала переливаться на соседние клетки, а затем — в море. Общий объём воды, скопившейся на острове — 2 кубические клетки.

Вот пример посложнее:

5 3 4 5
6 2 1 4
3 1 1 4
8 5 4 3

После дождя карта острова принимает следующую форму:

5 3 4 5
6 3 3 4
3 3 3 4
8 5 4 2

Общий объём скопившейся после дождя воды на таком острове составляет целых 7 кубических клеток!

Ваша программа должна читать входные данные из stdin.
В первой строке указывается количество островов K, после чего в следующих строках описываются эти K островов.
В первой строке описания острова задаются его размеры N и M — целые числа в диапазоне , разделённые пробелом.
В следующих строках описывается матрица NxM со значениями высот клеток острова, которые могут принимать значения из диапазона .

Вот пример входных данных:

3
3 3
4 5 4
3 1 5
5 4 1
4 4
5 3 4 5
6 2 1 4
3 1 1 4
8 5 4 3
4 3
2 2 2
2 1 2
2 1 2
2 1 2

Ваша программа должна выводить в stdout значения общего объёма воды, скапливающейся на острове после сезона дождей для каждого из входных примеров. Для приведённых выше данных, вывод программы должен быть следующим:

2
7
0

Уже несколько дней бьюсь и все решения мне кажутся громоздкими и неуклюжими.
И не уверен что полностью рабочими.
Можете подсказать, в какую сторону двигаться, что бы грамотно реализовать эту задачу?

botinag

Окт. 10, 2016 10:37:12

 def f(matrix):
    value = 0
    min_border = matrix[0][1]
    inner = []
    matrix_len = len(matrix)
    for i, row in enumerate(matrix, start=1):
        if i == 1 or i == matrix_len:
            min_border_candidate = min(row[1:-1])
        else:
            min_border_candidate = min(row[0], row[-1])
            inner.extend(row[1:-1])
        if min_border > min_border_candidate:
            min_border = min_border_candidate
    for x in filter(lambda x: x < min_border, inner):
        value += min_border - x
    return value

>>> m1 = [
...     [4, 5, 4],
...     [3, 1, 5],
...     [5, 4, 1]
... ]
>>> m2 = [
...     [5, 3, 4, 5],
...     [6, 2, 1, 4],
...     [3, 1, 1, 4],
...     [8, 5, 4, 3]
... ]
>>> m3 = [
...     [2, 2, 2],
...     [2, 1, 2],
...     [2, 1, 2],
...     [2, 1, 2]
... ]
>>> f(m1)
2
>>> f(m2)
7
>>> f(m3)
0

До ума доводите сами.

EvilRoot

Окт. 10, 2016 17:13:54

botinag
Я уже делал нечто подобное, но к сожалению такой подход не рабочий.
При размерах матрицы более 5 на 5 и высоте столбцов около 100, с завидной частотой выдает нули в ответе, чего очевидно не может быть.

  ==============
[[42 54 89 19]
 [79 20 67 56]
 [12 27 38 17]
 [ 2  7 71 80]]
0
 ==============
[[30 31 16 55 73 34 82]
 [ 3 12 21 19  8 61 97]
 [79 53 41 51 49 85 63]
 [57  9 16 29 56 48 44]]
0
 ==============
[[90 88 69 26  5 56 67 30]
 [37 32  5 34 61 96 25  7]
 [66  1 80 94 57 67 84  2]
 [46 32 48 35 39 21 13 61]
 [45 15 84 71 37 74 23  4]
 [21 42 45 15 73 15 96 78]
 [20  2 99 97 13 16 41 33]
 [44 31 91 93 31 81 85 45]
 [62 93 87 69 29 34 23 87]]
1
 ==============
[[51 72 75 70]
 [23 66 88 24]
 [12 17 94  8]
 [14 56 57 18]
 [94 97 81 50]
 [40 74 92 48]
 [13 11 73 86]
 [45 92 35 85]
 [46 57 80 76]]
0

Честно говоря даже не понимаю где дает ошибку. Мне кажется тут нужно использовать аналитический метод решения. Или использовать объектно-ориентированные подход. Потому я попросил метод грамотного решения или по крайней мере совет с чего лучше начать.

wi34rd

Окт. 16, 2016 08:29:22

Не скажу, что оптимально решил, но работает. http://pastebin.com/K8RXs4wy