Vùng hình chữ nhật trong một mảng

Question

Cho ma trận N * N có số 1 là 0 trong số đó và được cho một số nguyên k, phương pháp nào tốt nhất để tìm một vùng hình chữ nhật sao cho nó có k 1 trong đó?

Answer 1

Hãy xem xét vấn đề này đơn giản hơn:

Cho một vector có kích thước N chỉ chứa các giá trị 1 và 0, hãy tìm một dãy có chứa chính xác k giá trị của 1 trong đó.

Hãy để A là vector đã cho và S[i] = A[1] + A[2] + A[3] + ... + A[i], có nghĩa là có bao nhiêu 1s trong hậu tố A[1..i].

Đối với mỗi i, chúng tôi quan tâm đến sự tồn tại của j <= i sao cho S[i] - S[j-1] == k.

Chúng ta có thể tìm thấy điều này trong O(n) với một bảng băm bằng cách sử dụng các mối quan hệ sau:

S[i] - S[j-1] == k => S[j-1] = S[i] - k

let H = an empty hash table 
for i = 1 to N do 
    if H.Contains (S[i] - k) then your sequence ends at i 
    else 
    H.Add(S[i]) 

Bây giờ chúng ta có thể sử dụng để giải quyết vấn đề cho bạn trong O(N^3): cho mỗi chuỗi các hàng trong ma trận đã cho của bạn (có O(N^2) chuỗi các hàng), hãy xem xét trình tự đó để biểu diễn một vectơ và áp dụng thuật toán trước đó trên nó. Việc tính toán S là khó khăn hơn một chút trong trường hợp ma trận, nhưng không khó để tìm ra. Hãy cho tôi biết nếu như bạn cần thêm chị tiết.

Cập nhật: Đây là cách các thuật toán sẽ làm việc trên các ma trận sau, giả sử k = 12:

0 1 1 1 1 0 
0 1 1 1 1 0 
0 1 1 1 1 0 

xem xét hàng đầu tiên một mình:

0 1 1 1 1 0 

xem xét nó là vector 0 1 1 1 1 0 và áp dụng thuật toán cho vấn đề đơn giản hơn về nó: chúng tôi thấy rằng không có thêm từ nào lên tới 12, vì vậy chúng tôi tiếp tục.

Hãy xem xét hai hàng đầu tiên:

0 1 1 1 1 0 
0 1 1 1 1 0 

xem xét họ làm vector 0+0 1+1 1+1 1+1 1+1 0+0 = 0 2 2 2 2 0 và áp dụng các thuật toán cho bài toán đơn giản về nó: một lần nữa, không có dãy biết thêm rằng đến 12, vì vậy tiến lên.

Hãy xem xét ba hàng đầu tiên:

0 1 1 1 1 0 
0 1 1 1 1 0 
0 1 1 1 1 0 

xem xét họ làm vector 0 3 3 3 3 0 và áp dụng các thuật toán cho bài toán đơn giản trên đó: chúng ta thấy trình tự bắt đầu từ vị trí thứ 2 và kết thúc ở vị trí 5 là giải pháp. Từ đó chúng ta có thể lấy toàn bộ hình chữ nhật với sổ sách kế toán đơn giản.

Answer 2

Tôi có thể làm điều đó với O (N^3 * log (N)), nhưng chắc chắn giải pháp tốt nhất là nhanh hơn. Trước tiên, bạn tạo một ma trận N * N khác (ma trận ban đầu là A). Logic của B như sau:

B[i][j] - is the number of ones on rectangle in A with corners (0,0) and (i,j). 

Bạn có thể đánh giá B cho O (N^2) bằng cách lập trình năng động: B [i] [j] = B [i-1] [j] + B [ i] [j-1] - B [i-1] [j-1] + A [i] [j].

Bây giờ rất dễ giải quyết vấn đề này với O (N^4) bằng cách lặp qua tất cả các đáy phải (i = 1..N, j = 1..N, O (N^2)), left-bottom (z = 1..j, O (N)), và right-upper (t = 1..i, O (N)) và bạn nhận được số lượng những cái trong hình chữ nhật này với sự trợ giúp của B:

sum_of_ones = B[i][j] - B[i][z-1] - B[t-1][j] + B[t-1][z-1]. 

Nếu bạn nhận được chính xác k: k == sum_of_ones, thì hãy ra kết quả.

Để đăng nhập N^3 * (N), bạn nên tìm kiếm phía trên bên phải bằng tìm kiếm nhị phân (vì vậy không chỉ lặp lại tất cả các ô có thể).