View Full Version : [Q] Đếm số hình chữ nhật
Cho một lưói ô vuông m*n(m,n<=100) gồm 0 và 1. Hỏi có bao nhiêu hình chữ nhật được tạo bởi các ô 1.
Input : lưới m*n
Out :số hình cn
Vd
inp:
11
01
(m=n=2)
out:
3
real_time
12-01-2004, 22:40
ê! u xem lại kết quả xem hình như chỉ có 2 thôi chứ?? cái này thử làm bằng quy hoạch động xem?? nếu tôi làm tôi dùng đệ quy hơi lâu.
zizi1 thu*? QHD:
1) if A[i][j] == 0:
Bi[i][j] = 0;
Bj[i][j] = 0;
num[i][j] = num[i-1][j] + num[i][j-1] - num[i-1][j-1]
2) if A[i][j] == 1:
Bi[i][j] = Bi[i][j-1]+1
Bj[i][j] = Bi[i-1][j]+1
num[i][j] = (num[i-1][j] + num[i][j-1] - num[i-1][j-1]) + Bi[i][j] + Bj[i][j]
Kho*?i ta.o:
a) A[0][j] = 0 (j:0->n)
b) A[i][0] = 0 (i:0->m)
c) Bj[0][j] = 0 (j:0->n)
d) Bi[i][0] = 0 (i:0->m)
Đie^`n:
loop i: 1->m
loop j: 1->n
num[i][j] = ...........
end loop j
end loop i
Đa'p so^' la` num[m][n]
Lu*u y':
num[i][j]: so^' hi`nh chu*~ nha^.t con trong (1,1) -> (i,j)
Bi[i][j]: so^' hi`nh chu*~ nha^.t con chu*'a A[i][j] trong (i,1) -> (i,j)
Bj[i][j]: so^' hi`nh chu*~ nha^.t con chu*'a A[i][j] trong (1,j) -> (i,j)
Kho*?i ta.o:
a) A[0][j] = 0 (j:0->n)
b) A[i][0] = 0 (i:0->m)
c) Bj[0][j] = 0 (j:0->n)
d) Bi[i][0] = 0 (i:0->m)
==> zizi1 su*?a la.i la`:
Kho*?i ta.o:
a) num[0][j] = 0 (j:0->n)
b) num[i][0] = 0 (i:0->m)
c) Bj[0][j] = 0 (j:0->n)
d) Bi[i][0] = 0 (i:0->m)
cali ha`m QHD coi bo^. 0 đu'ng
ê! u xem lại kết quả xem hình như chỉ có 2 thôi chứ?? cái này thử làm bằng quy hoạch động xem?? nếu tôi làm tôi dùng đệ quy hơi lâu.
11: 1 hình
1: 1 hình
1
1 : 1 hình nữa
Vậy là 3 hình (hình vuông cũng là hình chữ nhật dzạ)
Tui lại nhìn ra tới .... 5 hình chữ nhật mới khổ chứ :
1x
0x
x1
0x
xx
01
11
0x
xx
01
Không hiểu đề bài xem thế nào là 1 hình chữ nhật tạo bởi các ô 1 nữa !?
À há, đúng rồi, tới 5 cái lận ;) Mình xem thiếu rồi.
Powered by vBulletin® Version 4.2.0 Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.