Bài toán chơi cờ trong Pascal
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (176.64 KB, 8 trang )
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,
• d > 0: nếu A thắng sau d nước đi.
Thí dụ:
Bài giải
Đây là một bài toán khó thuộc lớp các bài toán trò chơi, tuy nhiên lời giải là dễ hiểu và đặc
biệt là thuật giải bài toán này có thể vận dụng cho một số bài toán khác.
a. Trước hết chúng ta hãy giảm nhẹ yêu cầu của bài toán, cụ thể là chúng ta chỉ yêu cầu
xác định đấu thủ đi nước đầu tiên là A sẽ thắng (ghi đáp số là 1) hay thua (ghi đáp số là
0).
Phương án này có thể giải dễ dàng bằng quy hoạch động như sau:
Lần lượt điền các giá trị 0 và 1 vào các ô trong từng dòng của bảng, theo trật tự từ dòng
cao nhất, dòng thứ N đến dòng thấp nhất, dòng 1. Trên mỗi dòng ta lần lượt điền từ trái
qua phải, tức là từ cột 1 đến cột M. Gọi mảng chứa dữ liệu của bàn cờ là a, ta quy định
a[i,j] = 0 nếu xuất phát từ ô (i,j) đến lượt ai đi thì sẽ thua, ngược lại, a[i,j] = 1 thì người nào
đến lượt đi sẽ thắng.
Để tiện trình bày, ta sẽ gọi ô chứa trị 0 là ô 0 (ô không) hay ô (dẫn đến) thua , ô chứa trị 1
là ô 1 hay ô (dẫn đến) thắng.
Ta thấy dòng N sẽ chứa toàn 0, vì đó là các thế “cùng”, tức là các thế thua. Từ dòng N-1
trở xuống ta tính trị cho các ô như sau.
Từ ô (i,j), nếu có một cách di chuyển quân cờ đến ô 0 là ô đẩy đối phương vào thế thua, thì
người cầm quân sẽ thắng, ngược lại, nếu không có cách nào, hay với mọi cách đi người
cầm quân chỉ có thể di chuyển quân cờ đến các ô 1 thì anh ta sẽ thua, vì sau anh ta, đến
lượt đối phương sẽ được “hưởng” thế thắng tại các ô nhận trị 1.
Khung của lời giải thể hiện trong thủ tục run sẽ như sau:
1. Mở tệp input tab.inp để đọc dữ liệu vào.
2. Mở tệp output tab.out để chuẩn bị ghi kết quả.
3. Đọc số lượng test vào biến sotest.
4. Với mỗi test
4.1. Đọc các giá trị N, M, x và y từ tệp input tab.inp, trong đó N và M là kích thước bàn cở,
(x,y) là tọa độ xuất phát của quân cờ.
4.2. Gọi thủ tục tab để điền trị cho mảng a là mảng biểu thị bàn cờ.
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:
1. Đầu tiên ta duyệt các cột trước j, cụ thể là các cột k:=1..(j-1) và xét xem có thể di
chuyển quân cờ @ đến ô (i+k,k) để đảm bảo chắc thắng hay không. Quân cờ @ chuyển
được đến ô (i+k,k) khi và chỉ khi
(i) có thể chuyển @ đến dòng i+k vẫn nằm trong giới hạn của bàn cờ, tức là i+k ≤ N,
(ii) Nếu chuyển @ đến ô (i+k,k) thì người cầm quân chắc thắng, hay là người đi tiếp sẽ
thua, tức là a[i+k,k] = 0.
2.Tiếp đến ta duyệt các cột sau j, cụ thể là các cột k từ j+1 đến M theo cùng cách thức như
trên.
Nếu tìm được một ô thỏa hai điều kiện thắng (i) và (ii) thì ta gán trị cho a[i,j] = 1 với ý
nghĩa là người cầm quân đi từ ô (i,j) đó sẽ chắc thắng, sau đó dừng tủ tục value.
Ngược lại, nếu đã duyệt mọi cột k:= 1..j-1, j+1..M mà không tìm được ô nào thỏa hai điều
kiện thắng nói trên thì đành chọn ô tùy ý, miễn là đi được theo đúng luật chơi. Trong
trường hợp này ta phải gán trị a[i,j] = 0 với ý nghĩa là người cầm quân sẽ thua, sau đó dừng
thủ tục value.
{ xac dinh gia tri cho o a[i,j];
a[i,j] = 0: Ai di tu o do se thua
a[i,j] = 1: Ai di tu o do se thang }
procedrue value(i,j: integer);
var k: integer;
begin
a[i,j]:=1; { Gán trước trị thắng }
{ Duyet cac o truoc cot j }
for k:=1 to j-1 do
if i+k <= n { trong ban co } then
if a[i+k,k] = 0 then exit;
{ Duyet cac o sau cot j }
for k:=j+1 to m do
if i+k <= n { trong ban co } then
if a[i+k,k] = 0 then exit;
a[i,j]:=0;
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;
