Chương 3: CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ

ng 3 ươ Ế Ậ

ề ệ ồ ị ng:

ỉ ề ớ 1, thăm v2… Thu t toán ậ i khi t

2 (ch a thăm) k v i v ư c thăm.

ấ ả

1, r i tìm đ nh v ề ượ

i ti p t c tìm

i nào đó, không còn đ nh nào k v i v

ồ t c các đ nh đ u đ ỉ ỉ ề ớ i là ch a thăm thì quay tr l ở ạ ế ụ ư Ch CÁC THU T TOÁN TÌM KI M TRÊN Đ TH Ồ Ị 1. Duy t đ th theo chi u sâu * Ý t ưở 1 nào đó ch a thăm, thăm v - T đ nh v ư ừ ỉ i vi c thăm cho t l p l ớ ệ ặ ạ i m t đ nh v - N u t ộ ỉ ế ạ đ nh k ch a thăm khác c a v ề ư ỉ ủ i-1.

A B ế ắ ầ ừ ỉ đ nh A, thăm có th là: ể E N u b t đ u t thì th t ứ ự A, C, B, D, E

D C

* Thu t toán: ậ void DFS1(v) {

ể ề ữ ậ Tham(v); ChuaTham[v]=false; //ghi nh n là đã thăm v đ v sau không thăm n a. For (u˛ t c các đ nh u k v i v Ke(v)) // xét t ấ ả ề ớ ỉ If (ChuaTham[u]) DFS1(u); //neu u chua thăm, thăm u

} void DFS() {

ầ ấ ả t c các đ nh đ u ch a thăm. ề ư ỉ for (v ˛ V) ChuaTham[v]=true; //ban đ u t for (v˛ t c các dinh ấ ả V) //xét t if (ChuaTham[v]) DFS1(v); // neu đ nh v chua tham thi tham v ỉ }

* Ví d : Xét đ th cho trong hình 1 g m 13 đ nh, các đ nh đ c đánh s t 1 đ n 13 nh sau: ồ ị ụ ồ ỉ ỉ ượ ố ừ ư ế

Hình 1

1

t r ng các đ nh trong danh sách k c a đ nh v (Ke(v)) đ ế ằ ề ủ ỉ ỉ ế c s p x p theo th t i theo th t ứ ự chúng đ ầ ủ tăng d n c a c thăm c đánh l thi ả ỉ ố ượ ủ ặ ỉ ượ ắ ạ ứ ự ượ Gi ch s . Khi đó ch s m i (trong ngo c) c a các đ nh đ trong thu t toán tìm ki m theo chi u sâu. ỉ ố ớ ế ề ậ

ẽ ượ * Nh n xét: ậ - M i đ nh s đ ỗ ỉ - DFS1(v) thăm t ộ ầ ộ ứ ỉ ố ầ ầ

ộ DFS1 chính là s thành ph n liên thông c a đ th . ủ ồ ị c thăm đúng m t l n. ọ t c các đ nh thu c cùng m t thành ph n liên thông ch a đ nh v. S l n DFS g i ỉ ầ - Đ ph c t p c a thu t toán là O(n+m). ấ ả ố ộ ứ ạ ủ ậ

ề ộ ệ ồ ị ng:

ề ớ ư ợ ỉ ộ ỉ ợ ề ớ ư ợ ỉ i vi c thăm cho t ệ ặ ạ ấ ấ ả i c t t ồ ạ ấ ấ ả ớ t c các đ nh u (ch a thăm) k v i v vào hàng đ i. L y ấ t c các đ nh t (ch a thăm) k v i u vào hàng đ i… ợ ỗ i ti p t c tìm 2. Duy t đ th theo chi u r ng * Ý t ưở - T đ nh v nào đó ch a thăm, thăm v, c t t ừ ỉ ư hàng đ i m t đ nh u, thăm u, r i l t ừ Thu t toán l p l ộ ỉ ư ở ạ ế ụ ậ - N u t ỉ ế ạ đ nh k ch a thăm khác c a y (y là đ nh tr ỉ i khi hàng đ i r ng. i m t đ nh x nào đó, không còn đ nh nào k v i x là ch a thăm thì quay tr l ề ư ề ớ c khi đ n x). ế ướ ủ ỉ

* Thuật toán: void BFS1(v) {

ữ

f ) // xét t ể ề ậ t c các đ nh u k v i v ấ ả ề ớ ỉ

queue=f ; //khoi t o queue là r ng ỗ ạ push(queue,v); //c t v vào queue ấ ChuaTham[v]=false; //ghi nh n là đã thăm v đ v sau không thăm n a. while (queue „ {

v=pop(queue);//lay v tu queue Tham(v); For (u˛ t c các đ nh u k v i v ấ ả ề ớ ỉ

Ke(v)) // xét t If (ChuaTham[u]) { push(queue,u); ChuaTham[u]=false; } } }

void BFS()

2

{

ầ ấ ả t c các đ nh đ u ch a thăm. ề ư ỉ for (v ˛ V) ChuaTham[v]=true; //ban đ u t for (v˛ t c các dinh ấ ả V) //xét t if (ChuaTham[v]) BFS1(v); // neu đ nh v chua tham thi tham v ỉ }

c đánh l i theo th t chúng ồ ị ủ ặ ỉ ượ ạ ứ ự c thăm trong thu t toán tìm ki m theo chi u r ng. * Ví d : ụ Xét đ th xét trong hình 1, ch s m i (trong ngo c) c a các đ nh đ ỉ ố ớ đ ế ượ ề ộ ậ

ẽ ượ * Nh n xét: ậ - M i đ nh s đ ỗ ỉ - DFS1(v) thăm t ộ ầ ộ ứ ỉ ố ầ ầ ộ DFS1 chính là s thành ph n liên thông c a đ th . ủ ồ ị c thăm đúng m t l n. ọ t c các đ nh thu c cùng m t thành ph n liên thông ch a đ nh v. S l n DFS g i ỉ ầ - Đ ph c t p c a thu t toán là O(n+m). ấ ả ố ộ ứ ạ ủ ậ

ể ườ ỉ ườ ng đi t ủ ồ ị s đ n t. ế ườ ừ ng đi và ki m tra tính liên thông ng đi gi a hai đ nh: ữ s s và t là hai đ nh nào đó c a đ th . Hãy tìm đ ỉ ả ử ưở ng: ủ ụ ấ ả ộ ỉ ầ ng đi t ế t c các đ nh thu c cùng m t thành ph n liên thông v i ớ ộ i ượ ạ c l ườ ng đi, ta dùng thêm bi n Truoc[v] đ ghi nh n đ nh đi ườ ườ ế s đ n t, ng ừ ể ậ ỉ ự ng đi t ừ c đ nh v trong đ 3. Tìm đ a) Bài toán tìm đ Gi * Ý t G i th t c DFS(s) ho c (BFS(s)) đ thăm t ể ặ ọ s. N u sau khi th c hi n xong th t c mà Chuaxet[t]=true thì không có đ ệ ủ ụ ế thì có đ ế ng đi t tr ướ ỉ s đ n t. Đ ghi nh n đ ậ ể s đ n v. ế ừ ườ

* Cài đ t:ặ

ư

- DFS1(v) c n s a nh sau: ầ ử ….. If (ChuaTham[u]) {

Truoc[u]:=v; DFS1(u); //neu u chua thăm, thăm u }

- BFS(v) c n s a nh sau: ầ ử ư

3

….. If (ChuaTham[u]) {

Truoc[u]:=v; push(queue,u); ChuaTham[u]=false; }

Chú ý: Đ ng đi tìm theo BFS là đ s đ n t nh ng DFS thì không. ườ ườ ng đi ng n nh t theo s c nh t ấ ố ạ ắ ừ ư ế

ầ ế ồ ị ồ ồ t đ th g m bao nhiêu thành ph n liên thông và t ng thành ph n liên thông c a nó là g m ừ ủ ầ ầ b) Tìm các thành ph n liên thông c a đ th : ủ ồ ị Hãy cho bi nh ng đ nh nào? ỉ ữ

ng:

ưở ố ọ ế ủ ụ ố ầ ặ ầ ằ

ể ế ế ế ậ ỉ * Ý t - S thành ph n liên thông b ng s l n g i đ n th t c DFS1() ho c BFS1(). - Ta dùng bi n numConnect đ đ m s thành ph n liên thông và dùng bi n Index[v] đ ghi nh n ch ầ ố s c a thành ph n liên thông ch a đ nh v (có th dùng bi n ChuaTham[v] thay cho bi n Index[v] ) ể ứ ỉ ố ủ ể ế ế ầ

NG 3

ả ộ ố ộ ả ng (trong kho ng t 1 đ n 255). M t mi n c a b ng là t p h p t ộ ậ ế ậ ừ ị ố ề ủ ả ộ ợ ấ ả ằ duy t t ộ ầ ủ ứ ự ượ ề ộ trên xu ng d ộ ề ủ ụ ả ạ ề ề ỉ ủ ừ

2 2 2 ọ ộ i. Di n tích c a m t mi n là s ô thu c mi n đó. Thí d b ng: ố ệ ướ 2 1 1

ỉ ị ị ố 2 2 1 ề ệ

ả ầ ố ị ệ ỉ ủ ấ ị ề bàn phím) có d ng: ề ữ ệ ọ ừ ỉ ả ạ

ộ ấ ấ ắ ộ ố t k theo menu g m các ch c năng: ồ ị ố ủ ế ế ươ ứ file ng trình thi ừ

i bài toán b ng tìm ki m theo chi u r ng. ế i bài toán b ng tìm ki m theo chi u sâu. ế ề ộ ề ươ

i h n kích th BÀI T P CH ƯƠ Ậ * Bài 1 : Các mi n trên b ng ề Cho m t b ng ch nh t chia thành MxN ô vuông (M dòng, N c t). M i ô vuông ghi m t s nguyên ữ ỗ t c các ô có cùng giá tr s sao d ả ươ c sang nhau b ng cách đi qua các ô có chung c nh và có cùng giá tr s đang xét. Đ a cho chúng đi đ ị ị ố ch c a m t mi n là t a đ [dòng, c t] c a ô đ u tiên thu c mi n theo th t ả trái sang ph i ộ ệ ừ và t ộ 1 1 2 1 1 3 có 4 mi n, mi n tô màu xám (giá tr các ô là 2) có đ a ch [1, 3] và di n tích là 7. ề C n xác đ nh: ị S mi n c a m ng. ề ủ Mi n có di n tích l n nh t (ch rõ giá tr di n tích và đ a ch c a mi n). ớ ệ D li u vào cho trong file văn b n (tên file đ c t M N A[1, 1] A[1, 2]...A[1, N] A[2, 1] A[2, 2]...A[2, N] ...................................... A[M, 1] A[M, 2]...A[M, N] trong đó A[i, j] là giá tr s c a ô [i, j], các s trên cùng m t dòng ghi cách nhau ít nh t m t d u tr ng. Yêu c u ch ầ Đ c d li u vào t ọ ữ ệ Gi ả ằ Gi ả ằ ng trình. K t thúc ch ế K t qu tìm đu c đ a ra màn hình. ế ợ ư ả c: M, N <= 100. Gi ướ ớ ạ

4

c đánh s t ạ ượ ố ừ ng ng v i m c p. Cho bi ạ ế ượ ộ ố ặ ơ ồ ạ ươ c cho b i h g m M ở ệ ồ ế t ặ ớ 1 đ n N. S đ m ng đ ứ ị ủ ố ự ơ i ta c n chuy n m t b c thông đi p t ả ể ườ ạ ế ề ầ máy s đ n máy t. Đ đ m b o an toàn, ng ể ả ng truy n tin khác nhau (t c không có kênh nào) c a m ng đ ứ ỗ ệ ừ ề ườ ạ ườ ườ ề ng truy n đ ủ ộ ố c hi u là t ng chi phí trên các kênh c a nó. Đ n giá đ ng truy n t ề ủ i ta chuy n ể ượ ử c s ng truy n tin cùng đi qua m t s máy tính). Chi ề ừ ơ ườ ủ ổ ng truy n tin; cho phép hai đ ể c tính nh sau: ượ ứ ệ ơ ơ ị ề ườ ộ ệ ủ ể ằ ổ ổ ấ ề ạ ấ ạ ỏ ề ấ ộ ng truy n t c (m t cách an toàn) thông đi p t c đ n giá c a m ng là t ng đ n giá m i đ ạ ộ ọ ườ ệ ớ ơ ượ ượ ườ ủ ơ ổ i ta mong mu n m ng máy tính (m ng truy n tin nói trên th a mãn tính ch t an toàn theo nghĩa ố i m t máy b t kỳ khác. Khi m t máy b t kỳ luôn truy n đ ấ i ta tính đ ề ừ ộ m t i m t máy b t kỳ khác. ấ ớ A[i, j] chính là ầ ử ạ ả ộ ị * Bài 2. Cho m t m ng N (N <= 20) máy tính đ ế ộ kênh (đo n) n i tr c ti p gi a m t s c p máy trong m ng, m kênh t ạ ữ chi phí truy n 1 đ n v thông tin theo m i kênh c a m ng. Ng ộ ứ b c thông đi n này theo hai đ ườ ứ ệ d ng trong c hai đ ề ả ụ phí c a m t đ ượ ộ ườ máy s sang máy t đ ư V i hai máy s và t, cùng b c thông đi p có đ dài là 1 đ n v thông tin, đ n giá truy n cho c p (s, t) ặ ớ c tính b ng t ng chi phí chuy n thông đi p an toàn (b ng t ng chi phí c a hai đ đ ng truy n tin) ề ằ ượ là nh nh t. ỏ Ng ườ là t ừ ộ m t m ng an toàn, ng ạ ộ máy b t kỳ t ấ ộ Ma tr n đ n giá c a m ng là m ng hai chi u A có N dòng và N c t, mà giá tr ph n t ề ủ ơ ậ đ n giá t máy i sang máy j. ừ ơ

ọ ọ ữ ọ ồ ố c sau khi đã h c m t s môn h c khác. M i quan h đó đ ố ọ ọ ệ ượ ệ ể ộ ố ộ ả ộ ướ ệ ở ọ ỉ ọ ượ ề ọ ọ ớ ằ c d y xong tr c khi h c môn j (ngày k t thúc môn i ph i tr ế ướ ả ứơ ỉ ắ ầ ọ ộ ướ ọ ế ệ ướ t c nh ng môn h c này (n u không vi ph m quan h ế ề ọ ừ ờ ấ ả ữ ạ ọ ọ ộ c môn i3, …, môn ik-1 ph i d y tr ế ắ ế ướ ọ ả ạ ả ạ ướ ả ạ ế ươ ệ ng trình v i tên KT3.PAS làm các vi c sau: ả ế ắ ể ế ế ắ ế ấ ả ờ

câu 2, hãy tính xem m t h c sinh trong quá ộ ọ ắ ề ộ ọ ả ả ả ọ ồ ượ ứ ấ ở dòng th nh t, trong nhóm N ng ti không ố ố ượ ứ ố ơ ế ắ ế ứ ấ ả ố ố ớ ứ ấ ế ả ế ả ả ư ầ ố ố ố ứ ế ố ớ * Bài 3 : M t khóa h c g m N môn h c, môn h c i ph i h c trong ti ngày. Gi a các môn h c có m i quan h ả ọ tr c th c/sau: có môn h c ch h c đ ọ hi n b i m t m ng hai chi u A[i, j]; i, j = 1, …, N trong đó A[i, j] = 1/0 và A[i, i] b ng 0 v i m i i, A[i,j] = 1 khi và ch khi môn h c i ph i ả c ngày b t đ u môn j). Môn h c i đ ọ ượ ạ c môn h c j n u có m t dãy môn h c i1, i2, …, ik sao cho a[it, it+1] = 1, 1 <= t <= k-1, ph i d y tr ả ạ ọ ỗ c/sau thì trong m i i1=i và ik=j. N u có m t nhóm các môn h c t ng đôi m t không có quan h tr ộ ộ ế ệ ngày, v nguyên t c, ta có th h c đ ng th i t ể ọ ồ ắ v i các môn h c khác). M ng A[i, j] đ c g i là b t c n u có m t dãy các môn h c i1, i2,…, ik, k > ượ ọ ớ ả c môn c môn i2, môn i2 ph i d y tr 1, mà môn i1 ph i d y tr ả ạ ướ c môn i1. ik, môn ik ph i d y tr ướ Hãy vi t ch ớ Hãy xét xem m ng A có b t c hay không. N u m ng A không b t c, hãy tính xem khóa h c có th k t thúc trong th i gian nhanh nh t là bao ọ nhiêu ngày. Theo các h c b o đ m th i gian hoàn thành ng n nh t ấ ở ờ trình h c ph i h c đ ng th i trong m t ngày nhi u nh t bao nhiêu môn. ấ ờ ọ D li u vào đ c cho b i file text có tên MH.DAT trong đó s N ghi ở ữ ệ dòng ti p theo, dòng th i ghi N s A[i, 1], …, A[i, N] dòng cu i cùng ghi N s nguyên d ố ế l n h n 30, 1 <= i <= N; N <= 30. ớ K t qu ghi ra file TKB.DAT nh sau: dòng th nh t ghi s 1/0 tùy theo m ng A b t c / không b ư ế t c. N u dòng th nh t ghi s 0, ta m i ghi ti p k t qu câu 2 và 3. ắ ế ế ể i thi u K t qu câu 2 ghi ti p vào file TKB.DAT N+1 dòng nh sau: dòng d u ghi s T là s ngày t ế có th hoàn thành khóa h c, ti p theo là N dòng trong đó dòng th i ghi 2 s X, Y v i ý nghĩa môn h c ọ ể th i h c t ngày th X đ n ngày th Y (chú ý r ngY–X=ti–1). ứ ứ ọ ừ ọ ế ứ ằ

5

ố ế ế ư ờ ế ớ ộ ả ả ọ ứ ấ ả ọ ồ ộ i. i gi ng đ ng ch c u đ a ra m t l ả ươ ộ ờ ỉ ầ ư ố ọ ể ờ i t ả ươ

TKB.DAT

TKB.DAT

0 22 1 2 3 4 1 8 9 12 13 22 13 14 15 171 21 3

ậ ấ ề ướ ng đ ữ ị ủ ỗ ượ ọ ỗ ộ ủ ươ ỗ ổ ế ượ ươ ỗ ờ ử ụ c g i là t ổ ng n u t ế ừ ổ

ộ c 4x4 mà m i dòng và m i c t c a nó đ u là m t hình này ta c hình kia nh s d ng các phép bi n đ i sau: 1) đ i ch hai dòng; 2) đ i ch hai c t; ộ ữ

ng đ ng, b i vì đ i ch dòng 3 và 4 c a q 1 ta thu đ ươ c ượ ủ ở ổ

c ượ ế ổ

c q 2. ượ ữ ố ổ ở ở ị ng hay không? ươ ư ấ ả

ủ ủ c vi ứ ứ trong m t dòng đ ộ ế ề ượ ế ng đ ng); i d ng sau: ướ ạ ả ng phép bi n đ i k (k=0, n u hai hình vuông là không t ế ố ượ ươ ươ ế ổ ế ể ừ q 1 thu đ ầ ổ ầ ổ ế ụ ỉ ố ỉ ố ủ ế ổ ế ặ ộ ỗ ổ ụ ế ả

K t qu câu 3 ghi ti p vào file TKB.DAT nh sau: dòng th nh t ghi 2 s Z, W v i ý nghĩa trong ngày Z ph i h c W môn (W là s nhi u nh t các môn h c ph i h c đ ng th i trong m t ngày), ti p theo là ề ọ ấ m t dòng ghi tên các môn h c ph i h c đ ng th i trong ngày Z. ả ọ ồ Trong các câu 2 và 3, có th có nhi u l i gi ề ờ Ví d 1ụ MH.DAT 4 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 1 1 Ví d 2ụ MH.DAT 7 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 2 2 8 4 10 2 3 * Bài 4: Hình vuông Latinh Hình vuông la tinh c p 4 là ma tr n vuông kích th hoán v c a các ch cái A, B, C, D. Hai hình vuông la tinh đ có th thu đ ể 3) đ i tên hai ch cái. ổ Ví d : Hai hình vuông la tinh ụ A B C D A B C D q 1 = B D A C q 2 = B C D A C A D B C D A B D C B A D A B C là t ỗ ươ A B C D B D A C D C B A C A D B ti p đ n đ i ch c t 3 và 4 ta thu đ ỗ ộ ế A B D C B D C A D C A B C A B D cu i cùng, đ i tên hai ch C và D cho nhau (nghĩa là thay C b i D và thay D b i C) ta thu đ Yêu c u: Cho q 1, q 2 là hai hình vuông la tinh c p 4. Hãy xác đ nh xem hai hình vuông đã cho có ấ ầ t ng đ ươ D li u vào: file văn b n LATIN.INP có c u trúc nh sau: ữ ệ 4 dòng đ u tiên ch c các dòng c a hình vuông q 1; ầ 4 dòng ti p theo ch a các dòng c a hình vuông q 2; ế (các ph n t t li n nhau); ầ ử K t qu : Ghi ra file văn b n có tên LATIN.OUT d ả Dòng đ u tiên ghi s l ầ ề ộ Các dòng ti p theo ghi dãy các phép bi n đ i c n áp d ng đ t c q 2; thông tin v m t ượ phép bi n đ i bao g m: ch s c a phép bi n đ i, ch s hai dòng (c t) c n đ i ch ho c hai ch cái ữ ổ ồ c n đ i tên cho nhau. ầ Ví d : các file d li u và k t qu có th : ể ữ ệ LATIN.INP LATIN.OUT ABCD BDAC DCBA CADB ABCD BCDA CDAB DABC 3 1 3 4 2 3 4 3 C D

6

ạ 1 t c đánh s t i N, m t s ng i trong h có bi ớ ồ ộ ườ ượ ộ ố ế ị ọ ạ t c các m i quan h c a h cũng nh b n có m t thông tin r t đ c bi ạ ủ ọ ố ừ ớ ọ ử ệ ủ ọ ộ ố ố ậ ậ t m t thông tin nào m i h g i thông tin đó cho nhau. B n là m t ng ế t t ấ ả ọ ề ỉ t đ a ch ườ ấ i r t t mà ệ ọ ế t ộ ấ ặ ầ ộ ố ỉ t c h đ u bi ữ ậ ườ ể ạ i còn l ứ ố i I bi ế ị ứ ế ỉ ỉ ủ ấ ứ ườ ố ứ i c n cho h i th I không bi ế ị ớ ả ườ ầ ọ ầ ố t thông tin. Dòng th hai ghi ra ch s c a nh ng ng i đó. ỉ ố ủ ườ ữ ứ

* Bài 5: Truy n tin trên m ng ề Có m t nhóm g m N l p trình viên đ email c a nhau. Khi bi ộ quan tr ng và b n bi ư ạ ế ấ ả t. Hãy l p trình ch ra m t s ít nh t các l p trình viên c n cho h bi mu n cho t ấ ế i thông tin c a b n. thông tin sao cho nh ng ng t c nh ng ng i đó có th thông báo cho t ủ ạ ấ ả ữ ườ D li u cho trong file văn b n v i tên INFOR.INP trong đó dòng đ u ch c s N (N <= 1000), dòng ữ ệ ầ ớ ả th I trong N dòng ti p theo ch a danh sách các l p trình viên mà ng ủ ọ t đ a ch email c a h . ứ ậ t đ a ch c a b t c ai thì dòng này là dòng tr ng. N u ng ườ ế K t qu ghi ra file văn b n v i tên INFOR.OUT trong đó dòng đ u ghi s K là s ng ế ố ả bi ế Ví d :ụ INFOR.INP INFOR.OUT 62 31154 3146

ề ớ ố ươ ườ ươ ng x <= y sao cho N=xy. V i cách phân tích ng ho c b ng 0. N u nó ố ế ặ ằ c 2 s nguyên d ượ ớ ể ươ i nh ng thao tác trên. ng ta có th ch n m t cách phân tích nào đó và l p l ặ ạ ng đ u v 0 ề ng N đ u tìm đ ề nhhiên m i N1=(x-1)(y+1). S này có th d ố ự ộ c nh ng s nào. ữ c, hãy cho bi ượ ữ ố ướ ể ọ ớ ố ự ấ ứ nhiên N (N <= 10000) cho tr ớ tăng d n. t kê ra t c theo th t t c các s tìm đ ứ ự ầ ả ệ ượ ấ ả t ta có th sinh ra đ ể ế ộ ố ố

VE0.OUT 0 3 4 6 7 10

ậ ố ừ ố ướ ỗ ộ c đánh s t ủ ấ ị ậ ọ ặ ộ i N và tô màu các vòng tròn đó (có th có các vòng ớ ể ng, m i cung có m t màu i b ng các cung đ nh h ặ ạ ằ ố ừ ượ ằ ạ ắ ầ i N đ t vào trong các vòng ắ ể ứ ứ ớ ố ỉ ượ ỉ ượ cùng m t vòng tròn ộ ế i vòng tròn Q ớ c chuy n. ể ầ ượ ộ ể ộ ố ứ ấ ị ướ ể ậ ữ ệ

ầ ứ ứ vòng tròn Ai t i vòng tròn Bi. ố ỗ ừ ố ị ớ ộ ấ ố ế c hay không. * Bài 6: M i con đ ọ M t s t nhiên d ộ ố ự này ta s hình thành ra s t ẽ d ươ Bài toán: V i s t D li u vào cho trong file text v i tên VE0.INP trong đó ch a m t s duy nh t N. ữ ệ K t qu ghi ra file text VE0.OUT trong đó li ế Ví d :ụ VE0.INP 12 * Bài 7: Chuy n biể C u bé v N (N<=100) vòng tròn đánh s t 1 t ẽ tròn có màu gi ng nhau) sau đó n i t ng c p l ị ố ừ 1 đ n 100. nh t đ nh. Các màu c a cung và c a vòng tròn đ ế ủ C u bé ch n 3 s nguyên khác nhau L, K và Q n m trong ph m vi t 1 t ố ớ ừ tròn s L và K m i vòng tròn m t hòn bi sau đó b t đ u di chuy n theo quy t c sau : ỗ Bi ch đ c chuy n theo cung có màu trùng v i màu vòng tròn ch a bi th 2 ể Bi ch đ c chuy n theo chi u cung ể ề Hai viên bi không đ c đ ng th i ượ ồ ờ ở t các viên bi. t ph i di chuy n l n l Không nh t thi ả ấ Quá trình di chuy n k t thúc khi m t trong hai viên bi t ể ế Hãy l p trình xác đ nh cách di chuy n đ ch m d t quá trình sau m t s ít nh t các b ể ấ D li u vào: file BI.INP Dòng đ u : 4 s nguyên N L K Q ố Dòng th 2 : N s nguyên C1, C2, …, Cn, Ci là màu vòng tròn i. ố Dòng th 3 : S nguyên M (0<=M<=10000) M dòng sau : m i dòng 3 s nguyên Ai,Bi,Di xác đ nh cung màu Di đi t Các s trên m t dòng cách nhau m t d u cách. ộ K t qu : đ a ra file BI.OUT Dòng đ u : CO ho c KHONG cho bi ặ ả ư ầ ượ ế ế

t quá trình có k t thúc đ 7

c di chuy n t ể ố i thi u. ể ị ầ ứ ố ố ướ

ỡ ữ ậ ố ộ ả ặ ố ỗ ị i thì A[i, j] = 0. c MxN (M s dòng, N s c t) ô vuông. M i ô mang giá tr 0 ho c 1, ướ c l ượ ạ i này có th di chuy n đ n ô ấ ườ ừ ể ể ế i xu t phát t c hay không b ng cách di chuy n sang nh ng ô chung c nh không có mìn. i đó không th di chuy n đ n (X2, Y2) đ ể ữ ể ế ượ ỡ c thì hãy ch ra cách g ít ỉ ể ể ể ữ ể ể ế ấ ữ ệ ả ắ ầ ng ng có mìn ho c không có mìn, m i s cách nhau ở ứ ươ ế ồ ố ỗ ố ặ ắ

ươ ứ ớ ng ng v i đi đ c thì dòng th hai là s K t ứ ượ ấ ầ dòng th hai thì K dòng ti p theo, m i dòng i g m 2 s t ng ng v i ch s c t và c / không đi đ ươ ứ ỗ c. ượ ớ ố ồ ượ ố ế ố ở ng ng v i s mìn ít nh t c n ph i g . ả ỡ ớ ố ươ ỉ ố ộ ứ N u dòng đ u là CO thì dòng 2 ch a s nguyên xác đ nh s b ế Ví d :ụ BI.INP 5 3 4 1 2 3 2 1 4 8 2 1 2 4 1 5 4 5 2 5 1 3 3 2 2 2 3 4 5 3 1 3 5 1 BI.OUT CO 3 * Bài 8: G mìn Cho b ng hình ch nh t kích th n u ô (i, j) có mìn A[i, j] = 1, ng ế ô (X1, Y1) không có mìn, ki m tra xem ng (a) M t ng ườ ộ (X2, Y2) đ ạ ằ ượ (b) N u k t qu câu a là ng ườ ả ế ế nh t nh ng qu mìn đ anh ta có th di chuy n đ n (X2, Y2). ả D li u vào: file text GOMIN.INP Dòng đ u là 6 s M, N, X1, Y1, X2, Y2 cách nhau b i kho ng tr ng. ố M dòng ti p theo, m i dòng g m N s 0/1 t ỗ b i kho ng tr ng. ở ả D li u ra: file text GOMIN.OUT ữ ệ Dòng đ u ch a s 0/1 t ứ ố ầ N u là không đi đ N u có s K ch s dòng c a ô th i c n ph i g mìn. ủ ứ ứ ầ ế ế ỉ ố ả ỡ

ướ ồ ở ỉ ị ươ ế ế ặ ế ng G g m N đ nh xác đ nh b i ma tr n k A[N, N] trong đó A[i, j] = 1 n u ậ ng trình xác đ nh tính liên ị t kê ậ t s thành ph n liên thông trong G và li ế ố ủ ồ ị t ch ầ ế ệ * Bài 9: Cho m t đ th vô h ề ộ ồ ị c nh (i, j) Î G và A[i, j] = 0 n u (i, j) Ï G. Hãy cài đ t thu t toán và vi ạ thông c a đ th G. N u G không liên thông, hãy cho bi c th các thành ph n liên thông này. ụ ể ầ

ấ ướ ạ ộ ồ i MxN. M i ô có th ỗ ế ậ ượ ấ ấ c chia thành các m nh đ t theo d ng ô l ả i đ ạ ượ ấ ồ c s đ ạ ọ ể ồ ậ ợ ể ấ c đánh d u là 0. Hai ô g i là k nhau n u ế ọ ượ c c đánh d u là 0. Hãy * Bài 10: Tìm ki mế M t vùng đ t hình ch nh t đ ữ c đánh d u là 1, các ô còn l tr ng tr t đ ọ ượ ẽ ượ chúng có chung 1 c nh (ngang hay d c). M t khu đ t tr ng là t p h p các ô có th tr ng tr t đ ọ n m k nhau l n nh t nghĩa là các khu đ t tr ng phân cách nhau b i các ô đ ằ ộ ấ ồ ượ ề ấ ấ ớ ở

8

thi t r ng s l ng các ố ượ ng và ch rõ c th các khu đ t tr ng n m trong vùng đ t. Gi ấ ồ ụ ể ằ ấ ỉ ả ế ằ ố ượ xác đ nh s l ị ô khá l n.ớ

9