Sáng kiến kinh nghiệm Ứng dụng thuật toán loang trong việc giải quyết một số bài toán cho học sinh giỏi tỉnh khối 12

“Ứng dụng thuật toán loang để giải quyết một số bài toán cho học sinh giỏi 
tỉnh khối 12” 
 Phần I: MỞ ĐẦU 
 1. Lý do chọn đề tài: 
 Ngôn ngữ lập trình Pascal là một nội dung được đưa vào chương trình học 
của bậc THPT và cũng là một nội dung được áp dụng cho các kỳ thi chọn học 
sinh giỏi tỉnh, học sinh giỏi quốc gia bộ môn tin học. Chính vì vậy cần nghiên 
cứu sâu về các giải thuật để hướng dẫn cho các học sinh ôn tập một cách tốt nhất 
cho các kỳ thi là một trong những mục tiêu cần đạt được của người giáo viên. 
 Trong các kỳ thi tuyển học sinh giỏi tỉnh khối 12 hầu hết trong các đề thi 
đều có các bài toán cần sử dụng giải thuật đệ loang để giải quyết vấn đề. Đó là 
một dạng bài toán có ứng dụng khá phổ biến. Vậy nên, đã có rất nhiều tài liệu 
viết về nội dung này. Tuy nhiên, theo quan điểm, cách nhìn nhận của tôi việc 
phân tích các bài toán trong đó còn khá trừu tượng khiến người đọc khó hình 
dung, khó để hiểu và khó viết chương trình. 
Hiện nay, tại trường tôi việc hiểu và sử dụng giải thuật loang còn nhiều hạn chế, 
không những số học sinh tham gia bồi dưỡng hiểu và sử dụng được còn rất ít mà 
cả giáo viên tham gia bồi dưỡng cũng còn nhiều lúng túng khi giảng dạy phần 
nội dung này. Tôi cũng là một giáo viên tham gia bồi dưỡng học sinh giỏi, tôi 
nhận thấy cần nghiêm túc nghiên cứu nội dung này để đưa ra cách trình bày, 
cách phân tích mới giúp người đọc dễ hiểu, dễ biết và dễ viết chương trình. Để 
tạo điều kiện thuận lợi trong quá trình bồi dưỡng và qua quá trình bỗi dưỡng tôi 
đã đúc rút được một số kinh nghiệm về việc trình bày, phân tích bài toán, ứng 
dụng các giải thuật loang và cài đặt một số bài toán trong các đề thi học sinh giỏi 
khối 12 những năm gần đây. Với mong muốn người đọc dễ dàng tiếp cận được 
vấn đề . Vì vậy tôi chọn đề tài “Ứng dụng thuật toán loang trong việc giải 
quyết một số bài toán cho học sinh giỏi tỉnh khối 12” 
 để nghiên cứu. Hy vọng đề tài trở thành một tài liệu quý cho học sinh tham 
gia bồi dưỡng và cũng là tài liệu đáng tham khảo cho quý thầy cô trong quá trình 
 1 
“Ứng dụng thuật toán loang để giải quyết một số bài toán cho học sinh giỏi 
tỉnh khối 12” 
 Nghiên cứu về cú pháp, câu lệnh trong ngôn ngữ lập trình Pascal để cài đặt 
một số bài toán về loang. 
 7. Phương pháp nghiên cứu: 
 Sử dụng phương pháp nghiên cứu lý thuyết, phương pháp tìm kiếm, thu 
thập thông tin, tổng hợp, phân tích và so sánh, thiết kế và cài đặt chương trình. 
 8. Đóng góp mới của đề tài: 
 Về mặt khoa học: Đề tài sẽ trình bày một cách logic các khái niệm từ đơn 
giản đến trừu tượng, giới thiệu, phân tích các bài tập cơ bản giúp hiểu rõ bản 
chất của vấn đề, từ đó vận dụng để giải quyết các bài toán phức tạp. 
 Về mặt thực tiễn: Đề tài trình bày tương đối đầy đủ về khái niệm, các ví 
dụ của bài toán loang – phân tích ưu điểm của việc sử dụng thuật toán loang. các 
bài tập khá đa dạng giúp cho người đọc nắm bắt và hiểu rõ về ưu điểm của thuật 
toán, cách viết và sử dụng loang trong lập trình Pascal để giải quyết các bài toán. 
 3 
“Ứng dụng thuật toán loang để giải quyết một số bài toán cho học sinh giỏi 
tỉnh khối 12” 
thị và thêm các đỉnh kề với nó vào danh sách chờ duyệt. Phương pháp cài đặt 
này là “lập lịch” để duyệt các đỉnh theo thứ tự duyệt ưu tiên trên chiều rộng 
(đỉnh nào gần với đỉnh gốc sẽ được duyệt trước) 
 Vì nguyên tắc trên (đỉnh nào gần gốc sẽ được duyệt trước) nên thuật toán 
tìm kiếm theo chiều rộng BFS thường được dùng để tìm đường đi ngắn nhất 
giữa các đỉnh. 
 Chúng ta sẽ xây dựng một danh sách chứa các đỉnh đang chờ duyệt, tại mỗi 
bước chúng ta thăm đỉnh ở đầu danh sách và thêm những đỉnh kề với nó chưa có 
trong danh sách chờ vào cuối danh sách. 
 Vì nguyên tắc đó nên chúng ta có thể tổ chức danh sách chờ đó bằng cấu 
trúc dữ liệu hàng đợi (Queue). 
Ban đầu tất cả các đỉnh i (i = 1..n) đều đặt cờ chuaxet[i] = True. Nếu đỉnh nào 
xét rồi ta đặt cờ của đỉnh đó sang trạng thái False. 
 Procedure BFS(v); Tìm kiếm theo chiều rộng bắt đầu từ đỉnh v 
 Begin 
 QUEUE = ; {Khởi tạo QUEUE ban đầu là rỗng} 
 QUEUE <= v; {Nạp đỉnh v vào QUEUE} 
 Chuaxet[v]:=False;{Đỉnh v nạp vào QUEUE là đã xét rồi => cờ của v là 
False} 
 While QUEUE ≠ do 
 Begin 
 P <= QUEUE; {Lấy p từ QUEUE} 
 Thăm đỉnh p; 
 For u € Ke(p) do {Những đỉnh u chung cạnh với đỉnh p} 
 If Chuaxet(u) then {Nếu đỉnh u chưa xét đến} 
 Begin 
 QUEUE <= u; {Nạp u vào QUEUE} 
 5 
“Ứng dụng thuật toán loang để giải quyết một số bài toán cho học sinh giỏi 
tỉnh khối 12” 
- Cho MxN ô vuông. Mỗi ô vuông chứa tần số A hoặc B. Từ vị trí này có thể di 
chuyển qua vị trí kia nếu hai ô nằm trong vùng ô vuông có chung cạnh. 
 - Cho MxN ô vuông, mỗi ô vuông chứa tần số A hoặc B. Từ vị trí này có 
thể di chuyển qua vị trí kia nếu hai ô nằm trong vùng ô vuông có chung cạnh. 
Kiểm tra xem tọa độ hai điểm có liên thông hay không? 
Phân tích: 
 Yêu cầu thực chất của bài toán là kiểm tra xem từ ô [x1;y1] đến ô [x2;y2] có 
liên thông với nhau hay không. 
 Ta dễ nhận thấy để biết được hai ô có liên thông với nhau được hay không 
ta dùng thuật toán loang là dễ nhất. Ta bắt dầu “loang” từ ô [x1,y1], nếu “loang” 
đến được ô [x2,y2] thì liên thông, ngược lại không liên thông. 
 Hàng đợi phục vụ “loang” được thể hiện bởi mảng 2 chiều 
Q:Array[1..2,Mmax*NMax] of Byte; hàng thứ 1 của Q để lưu thông tin chỉ số 
hàng, hàng thứ 2 lưu thông tin của chỉ số cột của các ô khi nạp vào Q. 
 Mảng A lưu thông tin tần số phát sóng tại 1 ô vuông. 
 Ban đầu k:=A[x1;y1] 
 Mảng B dùng để đánh dấu những ô đã “loang” đến; khi ô [i,j] được “loang” 
đến thì B[i,j] được gán giá trị là True. Điều kiện để loang đến được ô [x,y] là 
A[x,y] =k và B[x,y]= false 
Sau khi thực hiện xong việc “loang”, nếu B[x2,y2] = True thì điều đó có nghĩa 
là từ ô [x1,y1] liên thông đến ô [x2,y2] ngược lại là không liên thông. 
Đoạn Code chính của chương trình. 
While not eof(f) do 
 Begin 
 Fillchar(b,sizeof(b),fales); 
 Readln(f,x1,y1,x2,y2); 
 K:= A[x1;y1]; 
 B[x1;y1]:=true; 
 7 
“Ứng dụng thuật toán loang để giải quyết một số bài toán cho học sinh giỏi 
tỉnh khối 12” 
Bài toán 2: Nông trại 
Tóm tắt: 
- Cho MxN ô vuông. Mỗi ô chứa một kí tự: kí tự “.” là ô trống, kí tự ‘#’ là hàng rào, kí tự 
“c” là gà, kí tự “f” là cáo. Một miền được gọi là liên thông nếu không đi qua ô có rào 
chắn. Cần đưa ra số gà và số cáo của trại biết rằng: Trong mỗi miền liên thông, nếu số gà 
lớn hơn số cáo thì số cáo bằng 0 ngược lại số gà bằng 0. 
Phân tích: Yêu cầu thực chất của bài toán là kiểm tra xem trong mỗi miền liên 
thông sau một đêm còn lại bao nhiêu gà, bao nhiêu cáo. 
 Ta dễ nhận thấy để xác định miền liên thông ta dùng thuật toán loang là 
thuận tiện nhất. Khi xét đến ô (x,y) nếu A[x,y]= “.” Thì đẩy vào hàng đợi, nếu 
A[x,y]= “c” tăng biến gà rồi đẩy vào hàng đợi, nếu A[x,y]= “f” tăng biến cáo và 
đẩy vào hàng đợi. lặp đi lặp lại cho đến khi hàng đợi rỗng. 
 Hàng đợi phục vụ “loang” được thể hiện bởi mảng 2 chiều 
Q:Array[1..2,Mmax*NMax] of Byte; hàng thứ 1 của Q để lưu thông tin chỉ số 
hàng, hàng thứ 2 lưu thông tin của chỉ số cột của các ô khi nạp vào Q. 
 Mảng A lưu thông tin kí tự tại 1 ô vuông. 
 Ban đầu k:=A[x1;y1] 
 Mảng B dùng để đánh dấu những ô đã “loang” đến; khi ô [i,j] được “loang” 
đến thì B[i,j] được gán giá trị .là True. Điều kiện để loang đến được ô [x;y] là 
A[x;y] =k và B[x;y]= false 
Sau khi thực hiện xong việc “loang”, nếu B[x2,y2] = True thì điều đó có nghĩa 
là từ ô [x1;y1] liên thông đến ô [x2;y2] ngược lại là không liên thông. 
 Đoạn code chính của chương trình 
 Procedure loang(sx,sy); 
 Var localF, localC: integer; 
 Procedure tham(x,y:integer); 
 Var d:integer; 
 9 
“Ứng dụng thuật toán loang để giải quyết một số bài toán cho học sinh giỏi 
tỉnh khối 12” 
 Bài toán 3: Đường đi của Robot (Đề thi HSG lớp 12 năm học 2009 - 2010, 
Tỉnh Hà Tĩnh) 
Một bảng hình chữ nhật có kích thước MxN (M,N nguyên dương và không lớn 
hơn 100) được chia thành các ô vuông đơn vị bằng các đường thẳng song song 
với các cạnh. Một số ô vuông nào đó có thể đặt các vật cản. Từ một ô vuông, 
Robot có thể đi đến một ô vuông kề cạnh với nó nếu ô vuông đó không có vật 
cản. Hỏi rằng nếu Robot bắt đầu xuất phát từ một ô vuông không có vật cản 
thuộc dòng K, cột L thì có thể đi đến được ô vuông không có vật cản thuộc dòng 
H, cột O hay không? Nếu có thì hãy chỉ ra đường đi qua ít ô vuông nhất. 
Dữ liệu vào là tệp văn bản BAI3.INP có cấu trúc: 
 - Dòng đầu tiên ghi các chữ số M, N, K, L, H, O. Các số ghi cách nhau ít 
nhất một ký tự trống; 
 - M dòng tiếp theo, mỗi dòng ghi N số 1 hoặc 0 tuỳ thuộc vào ô vuông 
tương ứng trong bảng hình chữ nhật nêu trên có vật cản hay không (ghi số 1 nếu 
có vật cản); các số trên mỗi dòng ghi liên tiếp nhau. 
Dữ liệu ra là tệp văn bản BAI3.OUT có cấu trúc: 
 Nếu Robot có thể đi được từ ô vuông thuộc dòng K, cột L đến ô vuông 
thuộc dòng H, cột O thì: 
 - Dòng đầu tiên ghi ‘Co duong di ‘; 
 - Các dòng tiếp theo, mỗi dòng ghi 2 số là chỉ số dòng và chỉ số cột của các 
ô vuông trong đường đi tìm được từ ô vuông thuộc dòng K, cột L đến ô vuông 
thuộc dòng H, cột O mà qua ít ô vuông nhất. Hai số trên mỗi dòng ghi cách nhau 
ít nhất một ký tự trống; 
 - Ngược lại, nếu Robot không thể đi được từ ô vuông thuộc dòng K, cột L 
đến ô vuông thuộc dòng H, cột O thì ghi ‘Khong co duong di’. 
Phân tích: 
Yêu cầu của bài toán thực chất là tìm đường đi từ ô [K,L] đến ô [H,O] sao cho 
qua ít ô vuông nhất. Ta dễ thấy thuật toán để xử lý một cách hợp lý nhất là thuật 
 11 
“Ứng dụng thuật toán loang để giải quyết một số bài toán cho học sinh giỏi 
tỉnh khối 12” 
 While dau<=cuoi do 
 Begin 
 i:=Q[1,dau]; 
 j:=Q[2,dau]; 
 dau:=dau+1; 
 If (i=h) and (j=o) then Exit;{Đến ô cần đến} 
 If (i>1) and (P[i-1,j]=0) and (A[i-1,j]=0) then 
 Begin 
 P[i-1,j]:=4;{o truoc do ben duoi} 
 cuoi:=cuoi+1; 
 Q[1,cuoi]:=i-1; 
 Q[2,cuoi]:=j; 
 End; 
 If (i<M) and (P[i+1,j]=0) and (A[i+1,j]=0) then 
 Begin 
 P[i+1,j]:=2; 
 cuoi:=cuoi+1; 
 Q[1,cuoi]:=i+1; 
 Q[2,cuoi]:=j; 
 End; 
 If (j>1) and (P[i,j-1]=0) and (A[i,j-1]=0) then 
 Begin 
 P[i,j-1]:=3; 
 cuoi:=cuoi+1; 
 Q[1,cuoi]:=i; 
 Q[2,cuoi]:=j-1; 
 End; 
 If (j<N) and (P[i,j+1]=0) and (A[i,j+1]=0) then 
 Begin 
 13 
“Ứng dụng thuật toán loang để giải quyết một số bài toán cho học sinh giỏi 
tỉnh khối 12” 
sinh giỏi và cũng là tài liệu cần cho các giáo viên tham gia bồi dưỡng học sinh 
giỏi các cấp. 
 Trong thời gian tới có thể mở rộng đề tài bằng cách bổ sung thêm các dạng 
toán thường gặp, trình bày các bài toán trong các kì thi học sinh giỏi, từ đó lập 
thành menu giúp học sinh học tập thuận lợi hơn. 
 Phần IV. TÀI LIỆU THAM KHẢO 
 1. Sách giáo khoa Tin học 11. NXB Giáo dục – năm 2014 
 2. Hồ sĩ Đàm. Tài liệu giáo khoa chuyên Tin 1. NXB Giáo dục – năm 2009 
 3. Nguyễn To Thành, Lập trình nâng cao trên ngôn ngữ Pascal. . NXB Đại 
 học Quốc gia – năm 2000 
 4. Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật. NXB Khoa học và Kĩ thuật 
 – năm 1998 
 Lê Minh Hoàng, giải thuật và lập trình, NXB Đại học sư phạm Hà Nội – năm 
 1999 
 15