Giả sử chúng ta có ma trận nhị phân 2D, bây giờ chúng ta phải tìm điểm bắt đầu và kết thúc của tất cả hình chữ nhật được lấp đầy bằng 0. Hình chữ nhật được tách biệt và không chạm nhau tuy nhiên chúng có thể chạm biên mảng. Hình chữ nhật chỉ có một phần tử cũng có thể.
Ví dụ, nếu đầu vào là ma trận 8x7 như trong bài, thì đầu ra sẽ là danh sách các tọa độ [top_row, left_col, bottom_row, right_col] của các hình chữ nhật 0.
Giải pháp:
- Hàm find_rect(i,j,a,output,index): quét từ (i,j) xuống và sang phải, đánh dấu đã duyệt bằng 5, xác định góc dưới phải.
- Hàm chính get_coord(a): duyệt toàn bộ ma trận, khi gặp 0 thì thêm [i,j] vào output, gọi find_rect.
- In output.
Ví dụ Code
def find_rect(i,j,a,output,index):
x = len(a)
y = len(a[0])
flag_col = 0
flag_row = 0
for m in range(i,x):
if a[m][j] == 1:
flag_row = 1
break
if a[m][j] == 5:
pass
for n in range(j, y):
if a[m][n] == 1:
flag_col = 1
break
a[m][n] = 5
if flag_row == 1:
output[index].append(m-1)
else:
output[index].append(m)
if flag_col == 1:
output[index].append(n-1)
else:
output[index].append(n)
def get_coord(a):
n = len(a)
op = []
idx = -1
for i in range(0,n):
for j in range(0, len(a[0])):
if a[i][j] == 0:
op.append([i, j])
idx = idx + 1
find_rect(i, j, a, op, idx)
print(op)
tests = [[1,0,1,1,1,0,1],
[1,1,0,1,1,1,1],
[1,1,1,0,0,1,1],
[1,0,1,1,0,0,1],
[1,0,1,1,0,1,1],
[1,0,1,0,0,0,0],
[1,1,1,0,0,0,1],
[1,0,1,1,1,0,1]]
get_coord(tests)
Đầu vào
[[1,0,1,1,1,0,1],[1,1,0,1,1,1,1],[1,1,1,0,0,1,1],[1,0,1,1,0,0,1],[1,0,1,1,0,1,1],[1,0,1,0,0,0,0],[1,1,1,0,0,0,1],[1,0,1,1,1,0,1]]
Đầu ra
[[0,1,0,1],[0,5,0,5],[1,2,1,2],[2,3,2,4],[3,1,5,1],[3,4,6,5],[5,3,6,5],[7,1,7,1],[7,5,7,5]]