Найти все целочисленные координаты заданного верхнего левого угла и нижнего правого угла прямоугольника


Вот проблема я работаю на

Есть \$Н \Время Н\$ поле, на котором ракеты обрушивались. Изначально все клетки в этой области имеют значение \$0\$. Там будут ракеты \$\ М$ обрушиваются на этом поле. Ракета \$я$е будет иметь силу \$P_i\$ и он будет влияют на все клетки в области с \$(A_i,B_i)\$ в верхнем левом углу и \$(C_i,D_i)\$ как нижний правый угол. Из-за ракет, стоимость всех клеток в этом прямоугольнике будет XORЭд с \$P_i\$.

После того, как все ракеты были засыпаны, вы должны выяснить значения в каждой ячейке этого поля.

Вот что я пробовала -

N = 3
M = 3
missiles = [[3,3,1,3,2],
[2,2,1,2,2],
[3,1,1,2,3]]

from itertools import product
# Logic
coords = {}
for i in missiles:
    Pi, Ai, Bi, Ci, Di = i
    for j in product(*[range(Ai-1, Ci), range(Bi-1, Di)]):
        if coords.get(j):
            coords[j] ^= Pi
            #[NxN[i[0]][i[1]] ^= Pi
        else:
            coords[j] = 0 ^ Pi

def print_grid(coords, N):
    count = 0
    for i in product(*[range(N), range(N)]):
        if i in coords:
            print(coords[i], "",end="")
        else:
            print(0, "",end="")
        count+=1
        if count%N==0:
            print()

print_grid(coords, N)

Выход -

3 3 3 
1 1 3 
3 3 0 

Именно то, чего я хочу, но мне было интересно, есть ли способ, чтобы оптимизировать его для больших входов. Любая помощь ценится.



Комментарии
1 ответ

Поскольку вы отметили, что используя numpy Это нормально для вас, вы можете упростить весь прямоугольник вычисления, используя свои передовые нарезки возможностей:

>>> # Let's define a square array
...
>>> a = np.array(range(25)).reshape((5, 5))
>>> a
array([[ 0, 1, 2, 3, 4],
[ 5, 6, 7, 8, 9],
[10, 11, 12, 13, 14],
[15, 16, 17, 18, 19],
[20, 21, 22, 23, 24]])
>>> # Advanced slicing allow us to extract blocks at once
...
>>> a[2:5, 1:3]
array([[11, 12],
[16, 17],
[21, 22]])

Вам просто нужно, чтобы инкапсулировать это поведение в классе для удобства использования:

import numpy as np

class BattleField:
def __init__(self, size):
self.field = np.zeros((size, size), dtype=int)

def receive_missile(self, power, top, left, bottom, right):
self.field[top-1:bottom, left-1:right] ^= power

def __str__(self):
return str(self.field)

if __name__ == '__main__':
missiles = [
[3,3,1,3,2],
[2,2,1,2,2],
[3,1,1,2,3],
]
field = BattleField(3)
for missile in missiles:
field.receive_missile(*missile)
print(field)


Другие точки для улучшения с ваш код включает в себя:


  • использовать более описательные имена, чем A, Bили C;

  • использование функций вместо кода верхнего уровня, для простоты тестирования и повторного использования;

  • с помощью if __name__ == '__main__' охранник для того, чтобы избежать какой-то код при импорте файла;

  • используя прямых значений параметров вместо того, чтобы паковать их в список и распаковка их в вызов функции (product(*[range(N), range(N)]) => product(range(N), range(N)));

  • используя dict.get его значение по умолчанию (coords[j] = coords.get(j, 0) ^ Pi) для упрощения кода.

10
ответ дан 19 марта 2018 в 09:03 Источник Поделиться