01/10/2018, 14:06

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 em cộng dồn trên mảng hai chiều, xong r chạy 4 vòng lặp để tìm kiếm :), nên bài này em chỉ làm được với n, m<=50. Độ phức tạp T(n^2*m^2). Mong các anh/ chị giúp em để có 1 thuật toán tối ưu hơn … Em cảm ơn <3.
P/s: chỗ em gạch dưới trong hình là ít nhất k(kg) ngô

Nguyễn Quốc Thái viết 16:08 ngày 01/10/2018

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

gist.github.com

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);
This file has been truncated. show original

Chu Văn Hưng viết 16:22 ngày 01/10/2018

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))

Bài liên quan
0