Hình chữ nhật tối đại trong ma trận 0/1.
Cho một ma trận biểu diễn bằng một mảng hai chiều kích
thước N ´ M ô và chỉ
chứa các kí tự 0 và 1. Tìm hình chữ nhật chứa toàn kí tự 1 và có diện tích lớn
nhất (gọi là hình chữ nhật tối đại).
Dữ liệu vào: Tệp văn bản CNMAX.INP:
-
Dòng đầu tiên: số
tự nhiên M,
3 £ M £ 70
-
Tiếp đến là các
dòng dài bằng nhau thể hiện một xâu gồm M kí tự là các chữ cái 0/1 viết liền
nhau.
-
Số dòng của tệp
input có thể lên tới 60 nghìn.
Dữ liệu ra: tệp văn bản CNMAX.OUT:
-
Dòng đầu tiên:
Diện tích của hình chữ nhật tối đại ABCD chứa toàn kí tự 1 tìm được.
-
Dòng thứ hai: Toạ
độ dòng và cột của đỉnh A.
-
Dòng thứ ba: Toạ
độ dòng và cột của đỉnh C.
|
|
j
|
k
|
l
|
m
|
n
|
o
|
p
|
q
|
r
|
|
u
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
v
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
0
|
|
w
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
|
x
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
|
y
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
|
Hình 4
|
||||||||
Thí dụ, với ma trận 5 ´ 9 chứa dữ
liệu như hình 4 thì hình chữ nhật tối
đại, tạm gọi là ABCD, có diện tích là 15 ô và có toạ độ điểm A là (dòng 2, cột 3) và điểm C là (dòng 4, cột 7) như trong hình 4.
|
CNMAX.INP
|
CNMAX.OUT
|
|
9
100000000
111111110
001111100
001111100
000000000
|
15
2 3
4 7
|
Chúng ta sẽ xây dựng một thuật toán giải bài toán
tổng quát hơn như sau:
Bài toán 8.3.1. Sân bay vũ
trụ
Người ta cần xác
định một vùng hình chữ nhật ABCD có diện tích lớn nhất và bằng phẳng trên hành
tinh Vega để xây dựng sân bay vũ trụ. Bạn được cung cấp một mảnh bản đồ hành
tinh Vega, nơi cần xác định vị trí xây dựng một sân bay. Mảnh bản đồ có dạng
hình chữ nhật gồm nhiều dòng điểm mã số từ 1 trở đi, mỗi dòng có đúng M điểm mã
số từ 1 đến M. Mỗi điểm được tô một màu thể hiện độ cao của điểm đó. Yêu cầu:
xác định hình chữ nhật ABCD chứa nhiều điểm đồng màu nhất.
Dữ liệu vào: Tệp văn bản CNMAX.INP.
-
Dòng đầu tiên: số tự nhiên M, 3 £
M £ 70.
-
Tiếp đến là các dòng dài bằng nhau thể hiện một xâu gồm M kí tự là các
chữ cái a..z viết liền nhau. Mỗi kí tự biểu diễn cho một màu thể hiện độ
cao của điểm tương ứng trên mảnh bản đồ hành tinh Vega. Hai kí tự khác nhau thể
hiện hai độ cao khác nhau. Hai điểm cùng độ cao được biểu diễn với cùng một kí
tự.
-
Số dòng của tệp input có thể lên tới 60 nghìn.
Thí dụ:
|
CNMAX.INP
|
CNMAX.OUT
|
|
20
bcccddddeabcvvvvvvvb
bbbbbccccccccccbbbbb
vvvvvcccccccccccccbb
vvcccccccccccccbbbbb
pppppccccccccccabbbb
pppppcccccccccczzzzz
ssccccccccccccczzzzz
sssssccccccccccccczz
hhhhhcccccccccczzzzz
uuuuuuuuczzzzzzzzzzz
|
80
2
6
9
15
|
Dữ
liệu ra: tệp văn bản CNMAX.OUT:
-
Dòng đầu
tiên: Diện tích của hình chữ nhật tối đại ABCD tìm được.
-
Dòng thứ hai: Toạ độ dòng và
cột của đỉnh A (ô Tây-Bắc).
-
Dòng thứ ba: Toạ độ dòng và
cột của đỉnh C (ô Đông-Nam).
Tính tổng quát của bài toán 8.3.1
thể hiện ở điểm sau:
-
Tệp không chỉ chứa các kí tự 0/1.
Bài giải
Do không thể đọc toàn bộ dữ liệu từ tệp CMAX.INP vào một mảng để xử lí nên chúng
ta sẽ đọc mỗi lần một dòng vào biến kiểu xâu kí tự (string) y. Vì hình
chữ nhật ABCD cần tìm chứa cùng một loại kí tự cho nên các dòng của hình sẽ
liên thông nhau. Để phát hiện tính liên thông chúng ta cần dùng thêm một biến
kiểu xâu kí tự x để lưu dòng đã đọc và xử lí ở bước trước. Tóm lại là ta
cần xử lí đồng thời hai dòng: x là dòng trước và y là dòng
đang xét.
Nếu xét các cột trong hình chữ
nhật cần tìm ta thấy chúng phải chứa cùng một loại kí tự. Ta dùng một mảng h
với ý nghĩa phần tử h[i]
của mảng cho biết tính từ vị trí thứ i
của dòng y trở lên có bao nhiêu kí tự giống nhau (và giống với kí tự y[i]). Ta gọi h[i]
là độ cao của cột i và mảng h khi đó sẽ được gọi là độ cao của dòng
đang xét.
Thí dụ, mảng tích luỹ độ cao của
dòng thứ 5 trong thí dụ đã cho sẽ là:
h
= (1,1,1,1,1,4,4,4,4,4,4,5,4,4,4,1,2,2,4,5)
|
A
|
|
|
|
|
|
|
B
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C
|
|
|
|
|
|
|
D
|
Biết độ cao, với hai dòng x và y chúng ta dễ dàng tính
được diện tích của mỗi hình chữ nhật ABCD chứa phần tử y[i] trên cạnh DC. Thật vậy,
giả sử ta đang xét kí tự thứ i =
8 trên dòng thứ 5 như đã nói ở phần trên. Ta có h[8] = h[7] = h[6] = 4; h[9] = h[10] = h[11] = 4; h[12] = 5; h[13] = h[14] = h[15] = 4; h[16] = 1,... Vậy thì, khi ta đi từ i về hai phía, trái và phải, nếu gặp các kí tự giống kí tự y[i]
còn độ cao thì không nhỏ hơn h[i] ta sẽ thu được hình chữ nhật lớn nhất
chứa kí tự y[i].
Với dòng thứ 5 là y đang xét, ta
có:
x = 'vvcccccccccccccbbbbb'; {dòng thu 4 }
y = 'pppppccccccccccabbbb'; {dòng thu 5 }
|
dòng
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
q
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
19
|
20
|
|
4
|
x
|
v
|
v
|
c
|
c
|
c
|
c
|
c
|
c
|
c
|
c
|
c
|
c
|
c
|
c
|
c
|
b
|
b
|
b
|
b
|
b
|
|
5
|
y
|
p
|
p
|
p
|
p
|
p
|
c
|
c
|
c
|
c
|
c
|
c
|
c
|
c
|
c
|
c
|
a
|
b
|
b
|
b
|
b
|
|
|
h
|
1
|
1
|
1
|
1
|
1
|
4
|
4
|
4
|
4
|
4
|
4
|
5
|
4
|
4
|
4
|
1
|
2
|
2
|
4
|
5
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
trong đó x chứa dữ liệu của dòng thứ 4, y chứa dữ liệu của dòng thứ 5 trong
tệp CNMAX.INP.
Từ điểm i = 8
dịch chuyển về bên trái ta thu được điểm c1 = 6; dịch chuyển về bên phải ta thu được điểm c2 = 15. Điều kiện để dịch chuyển là:
s
(y[c1]
= y[i]) and (h[c1] ³ h[i]), nếu qua trái
và
s
(y[c2]
= y[i]) and (h[c2] ³ h[i]), nếu qua phải.
Hai thao
tác trên được đặt trong hàm tính diện tích của hình chữ nhật ABCD lớn nhất chứa
điểm y[i]. Hàm cho ra ba giá trị:
s
c1: điểm
trái nhất hay là toạ độ cột của đỉnh D.
s
c2: điểm
phải nhất hay là toạ độ cột của đỉnh C.
s
Diện tích của
hình.
(*-------------------------------------------
Dien tich cua hinh chua diem y[i]
--------------------------------------------*)
function
DienTich(i: byte; var c1,c2: byte): longint;
begin
{Qua trai}
c1 := i;
while (y[c1-1] = y[i]) and (h[c1-1]
>= h[i])
do dec(c1);
{Qua phai}
c2 := i;
while (y[c2+1] = y[i]) and (h[c2+1] >=
h[i])
do inc(c2);
DienTich := h[i]*(c2
+ 1 - c1);
end;
Phần xử lí chính được đặt trong thủ tục Run.
Mảng h[1..m] lúc đầu được khởi trị toàn 0. Sau mỗi
lần đọc dòng y ta chỉnh lại độ cao h theo tiêu chuẩn sau.
Tại điểm i đang xét trên dòng y, nếu y[i] = x[i]
độ cao h[i] được tăng thêm 1. Ngược lại, nếu y[i]
¹ x[i] ta đặt lại độ cao h[i]
= 1.
{Chinh do cao}
for i := 1 to m do
if y[i] = x[i]
then inc(h[i]) else h[i] := 1;
Một vài chú giải
1.
Chúng ta sử dụng
phần tử h[0] = 0 và h[m+1] = 0 để chặn vòng lặp, cụ thể là để các điều kiện (h[c1-1] >= h[i]) và (h[c2+1] >= h[i]) trở thành false ở cuối vòng lặp.
2.
Một con đếm dòng d kiểu longint cho biết ta
đang xử lí dòng nào của tệp.
3.
Dòng x lúc đầu được khởi trị toàn dấu cách là
kí tự không có trong văn bản thể hiện tấm bản đồ.
4.
Mỗi khi xử lí
xong dòng y ta cần sao chép giá
trị của y
cho x để lưu
giữ cho bước tiếp theo. Khi đó x sẽ trở thành dòng trước.
5.
Mỗi khi tìm được
một hình chữ nhật, ta so sánh diện tích của hình với diện tích lớn nhất hiện có
(dtmax) để
luôn luôn đảm bảo rằng dtmax chính là diện tích lớn nhất trong vùng đã khảo sát.
Thủ tục Run được thiết kế theo sơ đồ sau:
1. Mở tệp dữ liệu CNMAX.INP;
2. Đọc giá trị chiều dài mỗi dòng vào biến m;
3. Khởi trị:
s
Con đếm dòng d := 0;
s
Dòng trước x toàn dấu cách;
s
Mảng chiều cao h toàn 0;
s
dtmax
:= 0; {diện tích max}
4.
Lặp cho đến khi
hết tệp CNMAX.INP:
4.1. Đọc dòng y;
4.2. Tăng con đếm dòng d;
4.3. Chỉnh độ cao h[1..m];
4.4. Xử lí mỗi kí tự y[i] của dòng y; i = 1..m.
4.4.1. Tìm diện tích dt của hình chữ nhật lớn
nhất chứa phần tử y[i]; cho giá trị ra là dt và hai chỉ số đầu trái c1 và đầu phải c2 thể hiện cạnh đáy của hình chữ
nhật.
4.4.2. Nếu dt > dtmax: chỉnh lại các giá trị
Diện tích
max: dtmax := dt;
Toạ độ
đỉnh A(Axmax,
Aymax):
Axmax
:= d – h[i] + 1;
Aymax
:= c1;
Toạ độ
đỉnh C(Cxmax , Cymax):
Cxmax := d;
Cymax := c2;
4.5. Sao chép dòng y sang x: x := y;
5.
Đóng tệp CNMAX.INP.
6.
Thông báo kết
quả.
procedure Run;
var i,c1,c2:
byte;
dt: longint;
begin
assign(f,fn); reset(f);
readln(f,m);
d := 0;
{Khoi tri cho
dong dau tien}
x := BL;
for i := 1 to m do x := x + BL;
{Khoi tri cho chieu cao}
fillchar(h,sizeof(h),0);
while not
eof(f) do
begin
readln(f,y);
inc(d);
{Chinh do cao}
for i := 1 to m do
if y[i] = x[i] then inc(h[i]) else
h[i] := 1;
for i := 1 to m do
begin
dt := DienTich(i,c1,c2);
if dt >
dtmax then
begin
dtmax := dt;
Axmax := d-h[i]+1; Aymax := c1;
Cxmax := d; Cymax
:= c2;
end;
end;
x := y;
end;
close(f);
Ket; {ghi ket
qua}
end;
Độ phức tạp tính toán
Giả sử tệp CNMAX.INP chứa n dòng,
mỗi dòng chứa m kí tự. Khi xử lí một dòng, tại mỗi kí tự thứ i
trên dòng đó ta dịch chuyển qua trái và qua phải, tức là ta phải thực hiện tối
đa m phép duyệt. Vậy, với mỗi dòng gồm m kí tự ta phải thực hiện m2 phép duyệt. Tổng cộng,
với n dòng ta thực hiện tối đa t = n.m2 phép duyệt.
(* Pascal
*)
(******************************************
CNMAX – Dien tich hinh chu nhat
toi dai
******************************************)
uses
crt;
const
fn =
'CNMAX.INP'; {Ten tep chua du lieu vao}
gn =
'CNMAX.OUT'; {Ten tep chua du lieu ra}
MN =
80; {chieu rong van ban}
BL =
#32; {dau cach}
NL =
#13#10; {xuong dong moi}
var f,g: text;
m: byte; {chieu rong tam ban do}
d: longint; {dem dong}
x,y: string; {x - dong tren}
{y – dong duoi}
h: array[0..MN] of
longint;
{chieu
cao cua cac cot}
dtmax: longint; {Dien tich max}
Axmax, Cxmax: longint; {toa do
diem A, C}
Aymax,Cymax: byte;
(*------------------------------
Ghi
file ket qua
--------------------------------*)
procedure Ket;
begin
assign(g,gn); rewrite(g);
writeln(g,Dtmax);
writeln(g,Axmax,BL,Aymax);
writeln(g,Cxmax,BL,Cymax);
close(g);
end;
(*--------------------------------------------
Dien
tich cua hinh chua diem y[i]
---------------------------------------------*)
function DienTich(i: byte; var
c1,c2: byte): longint;
tự viết
procedure Run; tự viết
BEGIN
run;
END.
Ứng dụng
Bài toán tìm hình chữ nhật tối đại thường dùng trong lĩnh vực đồ hoạ và
xử lí ảnh. Dưới đây liệt kê vài ứng dụng điển hình.
1.
Trong khi vẽ bản
đồ ta thường phải tìm một hình chữ nhật tối đại trong một vùng, chẳng hạn lãnh
thổ của một quốc gia để có thể viết các kí tự vào đó như tên quốc gia, tên châu
lục.
2. Trong hình học phân hình (fractal) ta thường phải tìm
một số hình vuông hoặc chữ nhật tối đại thoả mãn một số tiêu chuẩn cho trước để
làm mẫu.
Trong bài này, để trình bày vấn đề được đơn giản chúng ta đã thay mỗi
điểm bằng một kí tự.
Bài tập làm thêm
Bài T1. Với mỗi kí tự c
cho trước hãy tìm trong tệp CNMAX.INP một hình chữ nhật tối đại chứa toàn
kí tự c.
Bài T2. Với cặp giá trị (k, c) cho trước hãy tìm
hình chữ nhật tối đại chứa cùng một loại kí tự và đồng thời chứa điểm nằm trên
dòng k, cột c của tệp CNMAX.INP.
Không có nhận xét nào:
Đăng nhận xét