tìm thấy tất cả các lĩnh vực hình chữ nhật với tính chất nhất định trong một ma trận

Question

đưa ra một m ma trận n * với các giá trị có thể có của 1, 2 và null:

. . . . . 1 . . 
    . 1 . . . . . 1 
    . . . 2 . . . . 
    . . . . 2 . . . 
    1 . . . . . 1 . 
    . . . . . . . . 
    . . 1 . . 2 . . 
    2 . . . . . . 1 

Tôi đang tìm kiếm cho tất cả các khối B (chứa tất cả các giá trị giữa (x0, y0) và (x1, y1)) rằng:

• chứa ít nhất một '1'
• không chứa '2'
• không phải là một tập hợp con của một khối khác với các thuộc tính trên

Ví dụ:

Khu vực màu đỏ, xanh lá cây và màu xanh tất cả đều chứa một '1', không '2', và không phải là một phần của một khu vực lớn hơn. Có tất nhiên hơn 3 khối như vậy trong ảnh này. Tôi muốn tìm tất cả các khối này.

cách nhanh chóng để tìm tất cả các khu vực này là gì?

Tôi có giải pháp brute-force làm việc, lặp qua tất cả các hình chữ nhật có thể, kiểm tra xem chúng có đáp ứng được hai tiêu chí đầu tiên không; sau đó lặp qua tất cả các hình chữ nhật tìm thấy, loại bỏ tất cả các hình chữ nhật được chứa trong một hình chữ nhật khác; và tôi có thể tăng tốc độ đó bằng cách trước tiên loại bỏ các hàng và cột giống nhau liên tiếp. Nhưng tôi khá chắc chắn rằng có một cách nhanh hơn nhiều.

Answer 1

Cuối cùng tôi đã tìm thấy một giải pháp hoạt động gần như trong thời gian tuyến tính (có một yếu tố nhỏ tùy thuộc vào số lượng khu vực tìm thấy). Tôi nghĩ đây là giải pháp nhanh nhất có thể.

Lấy cảm hứng từ câu trả lời này: https://stackoverflow.com/a/7353193/145999 (hình ảnh cũng lấy từ đó)

Trước tiên, tôi đi trought ma trận theo cột, tạo ra một ma trận mới M1 đo số bước để cuối cùng '1' và một ma trận M2 đo số bước để cuối cùng '2'

tưởng tượng một '1' hoặc '2' trong bất kỳ của các khối màu xám trong hình trên

cuối cùng tôi có M1 và M2 tìm như thế này:

Không đi qua M1 và M2 ngược lại, bởi hàng:

tôi thực hiện các thuật toán sau đây:

foundAreas = new list() 

For each row y backwards: 
    potentialAreas = new List() 
    for each column x: 
     if M2[x,y]>M2[x-1,y]: 
      add to potentialAreas: 
       new Area(left=x,height=M2[x,y],hasOne=M1[x,y],hasTop=false) 
     if M2[x,y]<M2[x-1,y]: 
      for each area in potentialAreas: 
       if area.hasTop and area.hasOne<area.height: 
         add to foundAreas: 
          new Box(Area.left,y-area.height,x,y) 
      if M2[x,y]==0: delete all potentialAreas 
      else: 
       find the area in potentialAreas with height=M2[x,y] 
       or the one with the closest bigger height: set its height to M2[x,y] 
       delete all potentialAreas with a bigger height 

      for each area in potentialAreas: 
       if area.hasOne>M1[x,y]: area.hasOne=M1[x,y] 
       if M2[x,y+1]==0: area.hasTop=true 

tại foundAreas chứa tất cả các hình chữ nhật với các thuộc tính mong muốn .

Answer 2

Bạn có thể đến đâu đó giữa việc xem xét mọi hình chữ nhật và giải pháp thông minh phù hợp.

Ví dụ: bắt đầu từ mỗi 1 bạn có thể tạo hình chữ nhật và dần dần mở rộng các cạnh của nó ra ngoài theo 4 hướng. Dừng khi bạn nhấn 2, ghi hình chữ nhật này nếu (a) bạn phải dừng lại ở cả 4 hướng, và (b) bạn chưa từng thấy hình chữ nhật này trước đây.

Sau đó quay lại: bạn cần có thể tạo cả hình chữ nhật màu đỏ và hình chữ nhật màu xanh lá cây bắt đầu từ 1 gần phía trên cùng bên trái.

Thuật toán này có một số trường hợp xấu nhất. Một đầu vào bao gồm tất cả các lò xo 1 s. Vì vậy, nó cần phải được kết hợp với một số thông minh khác, hoặc một số hạn chế về đầu vào.

Answer 3

Xét bài toán một chiều đơn giản:

Tìm tất cả các chuỗi con của .2.1.1...12....2..1.1..2.1..2 trong đó có ít nhất một 1 và không 2 và không phải là chuỗi con của chuỗi như vậy. Điều này có thể được giải quyết trong thời gian tuyến tính, bạn chỉ cần kiểm tra nếu có một 1 giữa hai 2.

Bây giờ bạn có thể dễ dàng thích nghi với thuật toán này cho vấn đề hai chiều kích:

Đối 1≤i≤j≤n tổng tất cả các dòng i-j sử dụng pháp luật như sau: .+.=., .+1=1, .+2=2, 1+1=1, 1+2=2, 2+2=2 và áp dụng một trong những thuật toán thứ nguyên cho dòng kết quả.

Độ phức tạp: O (n²m).