task0.py - master - k2709/matrix_task

task0.py
145 строк5 KB
urik
Initial commit
06 янв 2025, 18:02
06 янв 2025, 18:029d2fadf
"""
После окончания работы над очередным шедевром кубизма художник решил определить,
какая площадь холста осталась незакрашенной. Холст имеет прямоугольную форму;
изображение состоит из n прямоугольников, расположенных в целочисленных координатах,
параллельно сторонам холста. Напишите программу, которая принимает ширину и высоту холста,
а также количество нарисованных на холсте прямоугольников n, и определяет
незакрашенную площадь холста.

В первой строке подаются высота и ширина холста – натуральные числа
w и h (1 ≤ w, h ≤ 100); во второй – целое число n,
количество прямоугольников (0 ≤ n ≤ 5000). Затем программа получает
n строк с координатами левого верхнего и правого
нижнего углов прямоугольников – x1, y1, x2, y2.
"""


"""
Это олимпиадная задача: чтобы решение было засчитано как правильное, код должен 
удовлетворять жестким требованиям – выполняться не более чем за 1 секунду, и использовать 
не более 16 Мб памяти. По этой причине эффективно решить эту задачу на Питоне очень сложно: 
решение «в лоб» на массиве максимального размера исполняется за 1,8-2 секунды, а решение с 
использованием множеств превышает лимит памяти.

Поскольку поэлементное обновление большого массива в Python происходит слишком медленно, 
эффективное решение заключается в обновлении массива «кусками»:

Ввод #1:
5 5
2
1 1 3 3
2 2 4 4
Вывод #1:
18
выполнение
5 5 
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]
2
1 1 3 3 
n_line1=1, n_col1=1, n_line2=3, n_col2=3
2 2 4 4 
n_line1=2, n_col1=2, n_line2=4, n_col2=4
[0, 0, 0, 0, 0]
[0, 1, 1, 0, 0]
[0, 1, 1, 1, 0]
[0, 0, 1, 1, 0]
[0, 0, 0, 0, 0]
18
   
Ввод #2:
6 7
3
0 0 5 5
1 1 4 4
2 2 3 3
Вывод #2:
17
Выполнение
6 7
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
3
0 0 5 5 
n_line1=0, n_col1=0, n_line2=5, n_col2=5
1 1 4 4
n_line1=1, n_col1=1, n_line2=4, n_col2=4
2 2 3 3 
n_line1=2, n_col1=2, n_line2=3, n_col2=3
[1, 1, 1, 1, 1, 0]
[1, 1, 1, 1, 1, 0]
[1, 1, 1, 1, 1, 0]
[1, 1, 1, 1, 1, 0]
[1, 1, 1, 1, 1, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
17
"""

# Это была не верная идея с такими названиями переменных, не отражающих сути
# number_columns, number_lines = map(int, input().split())
# arr = [[0 for width in range(number_columns)] for height in range(number_lines)]
# for i in range(number_lines):
#     print(arr[i])
# number_figures = int(input())
# for i in range(number_figures):
#     n_line1, n_col1, n_line2, n_col2 = map(int, input().split())
#     print(f'n_line1={n_line1}, n_col1={n_col1}, n_line2={n_line2}, n_col2={n_col2}')
#     for l in range(n_line1, n_line2):
#         arr[l][n_col1:n_col2] = [1] * (n_col2 - n_col1)
#
# for l in range(number_lines):
#     print(arr[l])
# print(number_columns * number_lines - sum(map(sum, arr)))

w, h = map(int, input().split())
# w количество столбцов
# h количество строк
arr = [[0 for w in range(w)] for h in range(h)]
for i in range(h):
    print(arr[i])
n = int(input())
for i in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    for x in range(x1, x2):
        arr[x][y1:y2] = [1] * (y2 - y1)

# arr[x][y1:y2] обозначает подмассив в строке x
# от столбца y1 (включительно) до y2 (не включительно)
# [1] * (y2 - y1) создает список из единиц длиной (y2 - y1)
# альтернатива - это создать нужный список для последующего присвоения
# генератором [1 for _ in range(y2 - y1)] или
# делать два вложенных цикла с прямым присвоением
#         for x in range(x1, x2):
#             for y in range(y1, y2):
#                 arr[x][y] = 1
#

for i in range(h):
    print(arr[i])
print(w * h - sum(map(sum, arr)))


# Здесь переделана логика движения по строкам и столбцам
# w, h = map(int, input().split())
# arr = [[0 for w in range(w)] for h in range(h)]
# for x in range(h):
#     print(arr[x])
#
# n = int(input())
# for i in range(n):
#     x1, y1, x2, y2 = map(int, input().split())
#     print(f'x1={x1}, y1={y1}, x2={x2}, y2={y2}')
#     for y in range(y1, y2+1):
#         arr[y][x1:x2+1] = [1] * (x2 + 1 - x1)
# for i in range(h):
#     print(arr[i])
# print(w * h - sum(map(sum, arr)))