Thuật toán tối ưu cho bài toán tìm kiếm trên mảng hai chiều

Bài này mình chưa nghĩ kĩ, mới chỉ đọc đề của bạn thôi, nhưng đây là ý tưởng ban đầu, mình chưa kiểm tra những trường hợp lạ, nên chưa chắc đã đúng nhé.

Ý tưởng là, biến mảng gốc thành 1 mảng khác, mỗi ô chứa tổng số từ góc trên bên trái đến ô đó. vd:
A
5 4 0

4 7 0

0 0 2

trở thành

B
5 9 9
9 20 20
9 20 22

Tính các ô ở cạnh trên và bên trái trước, mỗi vị trí là giá trị vị trí trước cộng giá trị ở mảng gốc của vị trí đó.
B(0, i) = B(0, i-1) + A(0, i) và B(i, 0) = B(i-1, 0) + A(i, 0)

Tính các ô sau:
B(x, y) = B(x - 1, y) + B(x, y - 1) + A(x, y) - B(x-1, y-1)

Sau khi tính tất cả các ô, tìm các ô có giá trị lớn hơn bằng giá trị cần tìm
Với mỗi ô lọc được, tạo 1 hình chữ nhật với 5 giá trị (t, l, b, r, v). T là trên (top), L là trái (left), b là dưới (bottom), r là phải (right) và v là giá trị ô (value).

Với mỗi hình chữ nhật này, thử xem có cắt đc dòng trên cùng bằng cách tính V = v - B(t, r), nếu V lớn hơn giá trị cần tìm, tức là cắt đc. Tương tự thử xem có thể cắt đc cột bên trái. Sau đó thử cắt cả 2. Nếu cắt được thì thêm hình chữ nhật đã được cắt vào danh sách các hình chữ nhật tìm đc và bỏ đi hình chữ nhật gốc.

Lặp lại quá trình cắt cho đến khi lượng hình chữ nhật không đổi.

Sắp xếp danh sách các hiình chữ nhật dựa trên giá trị và diện tích (càng nhỏ càng tốt).

Hình chữ nhật đầu tiên sau khi sắp xếp là hình chữ nhật cần tìm.

Mình không để ý kĩ lắm về độ phức tạp, nhưng mình đoán là trong khoảng O(n * m), đoạn cắt hơi lằng nhằng chút, không rõ là phức tạp ra sao. Cách làm này dùng dynamic programming 1 chút, và mình chưa thử với các trường hợp lớn, bạn tự thử nhé.

Code sơ bộ, đọc từ std::cin vì mình pipe file từ console, có thể thay bằng ifstream nếu mở file

https://gist.github.com/anonymous/fd44be71882014c8e8b8119155df8dce

rect.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

std::vector<std::string> splitString(const std::string& str, char d)
{
	std::vector<std::string> result;
	auto s = str.begin();
	auto e = std::find(s, str.end(), d);

Mình nghĩ là dùng chặt nhị phân để tìm chiều dài và rộng của hình chữ nhật. Đpt O(nmlog(m)*log(n))