Ngày xuân lập trình chơi cờ bảng
Nguyễn Xuân Huy
Bài toán Tab game (Cờ bảng)
Cờ bảng gồm một bảng N x M ô vuông đơn vị và một quân cờ kí hiệu là @. Các dòng của
bảng được mã số 1..N từ dưới lên, các cột được mã số 1..M từ trái qua phải. Lúc đầu quân
cờ @ được đặt tại một ô (x,y) gọi là ô xuất phát. Hai đấu thủ là A và B lần lượt di chuyển
quân cờ, A luôn đi trước trong mọi ván cờ. Luật chơi như sau:Đến lượt ai, người đó có
nhiệm vụ di chuyển quân cờ đang đặt tại cột i sang cột k ≠ i theo cách sau:
- Thoạt tiên chuyển dọc quân cờ lên k dòng, nếu quân cờ chưa ra khỏi giới hạn bàn cờ thì
tiếp tục chuyển quân cờ (rẽ phải hoặc trái) sang cột k.
- Đấu thủ nào, đến lượt mình, không tìm được cách nào di chuyển quân cờ thì sẽ thua. Ván
cờ kết thúc.
Thí dụ, với bàn cờ 10 x 4, quân cờ @ đặt tại vị trí (5,3) thì A có thể di chuyển quân cờ đến
các ô (6,1), (7,2) hoặc (9,4).
Yêu cầu: Hãy cho biết A có thể thắng hay không? Trong trường hợp A thắng, hãy cho biết
A có thể thắng sau tối đa bao nhiêu nước đi với giả thiết là hai đấu thủ A và B đều chơi rất
giỏi và mỗi lượt A hoặc B đi được gọi là một nước đi.Trong thí dụ trên, khi quân cờ được
đặt tại vị trí xuất phát (5,3) thì A thua.Ngược lại, nếu chọn vị trí xuất phát là (4,3) thì A có
thể thắng sau 2 nước đi (xem hình 1).
Dữ liệu vào: Tệp văn bản tab.inp:
Dòng đầu tiên là số lượng test s, 1 ≤ s ≤ 10.
Tiếp đến là s dòng, mỗi dòng là một test gồm 4 số tự nhiên cách nhau ít nhất một dấu
cách, N M x y, trong đó
• N - số lượng dòng của bảng, 1 ≤ s ≤ 200,
• M - số lượng cột của bảng, 1 ≤ s ≤ 50,
• x - tọa độ dòng xuất phát của quân cờ,
• y - tọa độ cột xuất phát của quân cờ.
Dữ liệu ra: Tệp văn bản tab.out:
Gồm s dòng, dòng thứ i chứa kết quả của test thứ i, cụ thể là chứa duy nhất một số tự
nhiên d với nghĩa sau,
• d = 0: nếu A thua,

4.3. Ghi a[x,y] là kết quả chơi ván cờ của đấu thủ A ứng với test đã cho với giả thiết là A
đi trước.
5. Đóng các tệp input và output.
procedure run;
var i: integer;
begin
assign(f,fn); reset(f);
assign(g,gn); rewrite(g);
readln(f,sotest);
for i:=1 to sotest do
begin
readln(f,n,m,x,y); tab;
writeln(g,a[x,y]);
end;
close(f); close(g);
end;
Thủ tục tab được thể hiện như sau,
1. Khởi trị toàn 0 cho mảng a.
2. Với mỗi dòng từ N-1 đến 1
Với mỗi cột từ 1 đến M
Điền trị cho ô a[i,j] theo thủ tục value(i,j).
3. Nhận a[x,y] làm đáp số. Dừng thủ tục.
procedure tab;
var i,j: integer;
begin
fillchar(a,sizeof(a),0);
for i:=n-1 downto 1 do
for j:=1 to m do value(i,j);
end;
Thủ tục điền trị cho ô (i,j), value(i,j) hoạt động như sau:

end;
Thuật toán trên có tên gọi là thuật toán min-max.
Chương trình hoàn chỉnh cho phương án đầy đủ cuối cùng sẽ như sau.
(* Phuong an day du *)
program tab;
uses crt;
const
fn = 'tab.inp'; gn = 'tab.out';
bl = #32; nl = #13#10;
nn = 201; mm = 51;