[Q] Đếm số hình chữ nhật

[zizi1]

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]

ê! 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.

[bete]

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)

[bete]

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)

[bete]

cali ha`m QHD coi bo^. 0 đu'ng

[daem0n]

ê! 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ạ)

[bete]

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 !?

[daem0n]

À há, đúng rồi, tới 5 cái lận ;) Mình xem thiếu rồi.