Đệ quy quay lui trên mảng 2 chiều và kỹ năng cài đặt
Trương Thị Thu Hường
Duyệt đệ quy là một trong những chiến lược đểgiải quyết nhiều bài toán, đặc biệt là các bài
toán đòi hỏi liệtkê mọi cấu hình thoả mãn. Thuật toán đệ quy và các vần đề xungquanh đệ
quy đã được nhiều tác giả đề cập đến. Trong bài viết này,tôi cũng sẽ trở lại với chủ đề đệ
quy, nhưng là đệ quy quay luitrên mảng hai chiều và kỹ năng cài đặt thông qua một số bài
toán cụthể.
Yếu tố mấuchốt trong một thủ tục đệ quy là điều kiện duyệt và điểm dừng. Vớiđặc trưng
của mảng hai chiều là phần tử mảng được xác định bằnghai giá trị hàng và cột, thông
thường chúng ta vẫn sử dụng cặp giátrị (i,j) (hàng, cột của 1 ô) làm bướcduyệt khi gọi thủ
tục đệ quy.
Một số bàitoán như: tìm đường đi từ ô (i
0
, j
0
) đến ô (i
k
,j
k
) với 4 khả năng đi tới các ô chung
cạnh như bài toán Mãđi tuần đã rất quen thuộc với chúng ta. Mặt khác, các bài toán sửdụng
thuật giải này đều có điều kiện duyệt hay điểm dừng khá rõràng và việc trả lại giá trị cũng
không quá phức tạp nên các bạnsẽ dễ dàng cài đặt được. Sau đây, tôi muốn giới thiệu với
các bạnmột bài toán được giải quyết theo phương pháp duyệt đệ quy quaylui, nhưng trong
khi cài đặt chúng ta cũng có đôi điều cần lưu ý.
Bài toán:
ở một nướcnọ do các đội bóng đá thiếu tinh thần thi đấu nên số trận hoà rấtnhiều. Ban tổ
chức quyết định thay đổi luật để kích thích các độithi đấu tích cực hơn. Giải sẽ tổ chức thi
đấu vòng tròn nghĩa làmỗi đội đều phải thi đấu với tất cả các đội khác đúng một trận.Nếu
hoà, cả hai đội đều bị 0 điểm. Đội thắng sẽ được 3 điểm vàđội thua cũng được 1 điểm. Do
sơ xuất của ban tổ chức, bảng kếtquả thi đấu của tất cả các đội đã bị nhoè, một số chỗ

Const inp=’INP.TXT’;
out=’OUT.TXT’;
Max=21;
C1:Array[1..3]of byte=(0,1,3);
C2:Array[0..3]of byte=(0,3,0,1);
Type arr=array[1..Max,1..Max] of shortint;
var a: arr; OK: Boolean;
n,io,jo:byte; g: text;
Procedure Docfile;
var i,j: byte;
begin
fillchar(a,sizeof(a),0);
assign(g,inp);reset(g);
readln(g,N);
for i:=1 toN do
begin
for j:=1 to N+1 do read(g,a[i,j]);
Readln(g);
end;
close(g);
end;
Procedure Sualai2(var a:arr);
var i,j,d,vt,s: byte;
Begin fori:=1 to N do
forj:=1 to N do
if A[i,j] in [0,1,3] then a[j,i]:=c2[a[i,j]];
fori:=1 to N do
begin
s:=0; d:=0;
forj:=1 to n do

If (a[i,j]<>0) and (a[i,j]<>1) and (a[i,j] <>3) then
begin
thulai:=false; exit;
end;
end;
if a[i,n+1]<>s then
begin
thulai:=false; exit;
end;
end;
end;
Procedure ghinhan(a:arr);
var i,j: byte;
Begin Ifthulai(a) then
for i:=1 to N do
begin
for j:=1 to N+1 do write(g,a[i,j]:3);
writeln(g);
end;
End;
Function KT(a:arr):Boolean;
var i,j:byte;
Begin KT:=true;
for i:=1 to N do
For j:=1 to N+1 do
If a[i,j]=-1 then beginkt:=false; exit; end;
end;
Procedure Tim(var io,jo: byte);
var i,j:byte;
Begin io:=0;jo:=0;