Tìm tất cả các hình chữ nhật được điền bằng 0 bằng Python

Giả sử chúng ta có một ma trận 2D nhị phân, bây giờ chúng ta phải tìm điểm đầu và điểm cuối của tất cả các hình chữ nhật được tô bằng 0. Chúng ta phải lưu ý rằng các hình chữ nhật được tách biệt và không chạm vào nhau tuy nhiên chúng có thể chạm vào ranh giới mảng. Một hình chữ nhật chỉ có một phần tử duy nhất cũng có thể.

Vì vậy, nếu đầu vào giống như -

thì đầu ra sẽ là [[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]]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm find_rect (). Điều này sẽ lấy i, j, a, output, index
• x:=số hàng
• y:=col count
• flag_col:=0
• flag_row:=0
• đối với m trong phạm vi từ i đến x, thực hiện
  • nếu a [m, j] giống với 1 thì
    • flag_row:=1
    • break
  • nếu a [m, j] giống 5 thì
    • không làm gì cả
  • đối với n trong phạm vi j đến y, thực hiện
    • nếu a [m, n] giống 1 thì
      • flag_col:=1
      • break
    • a [m, n]:=5
  • nếu flag_row giống 1, thì
    • chèn m-1 vào cuối đầu ra [chỉ mục]
  • nếu không,
    • chèn m vào cuối đầu ra [chỉ mục]
  • nếu flag_col giống 1, thì
    • chèn n-1 vào cuối đầu ra [chỉ mục]
  • nếu không,
    • chèn n vào cuối đầu ra [chỉ mục]
• Từ phương pháp chính, hãy thực hiện như sau -
• n:=kích thước của một
• op:=một danh sách mới
• idx:=-1
• đối với tôi trong phạm vi từ 0 đến n, thực hiện
  • đối với j trong phạm vi 0 đến kích thước của [0], thực hiện
    • nếu [i, j] giống 0, thì
      • chèn [i, j] vào op
      • idx:=idx + 1
      • find_rect (i, j, a, op, idx)
• hiển thị op

Mã mẫu

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

 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 cho n trong phạm vi (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 (thử nghiệm)  
 Đầ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]]