Các bài toán di chuyển

Nguyễn Xuân Huy

Trong các kỳ thi học sinhgiỏi ta thường gặp một số bài toán có yếu tố di chuyển. Nội dung của những bàitoán này thường được phát biểu như sau: MộtRobot di chuyển trong một mê cung hình chữ nhật ABCD được chia thành các ôvuông đơn vị. Gốc toạ độ đặt tại điểm A (0,0). Robot đứng tại điểm R(x0,y0) làvị trí xuất phát, mặt hướng về phíaBắc, tức là nhìn về phía cạnh BC như trong Hình 1. Biết luật di chuyển củaRobot, hãy xác định vị trí kết thúc của Robot.

Bài toán trên có thể được bổ sung thêm một số điều kiệnnhư đặt năng lượng hoặc đặt bẫy tại một số ô. Nếu Robot gặp năng lượng thì sựvận động của nó sẽ mạnh hơn, chẳng hạn mỗi bước đi của nó có thể qua 2 ô, ngượclại, khi Robot gặp bẫy, sức khoẻ của nó suy giảm, bước di chuyển của nó sẽ ngắnhơn trước. Bố trí thêm các bức tường ngăn để tạo mê cung, ta có thể biến hoábài toán thành nhiều dáng vẻ khác nhau. Đương nhiên người ta khôngbịa ranhững bài toán để hành hạ học sinh. Đây là những bài toán điều khiển Robot cóthực trong đời thường. Giải hoặc làm chủ được các thuật toán di chuyển nói trênchúng ta sẽ có thể có những đóng góp giá trị cho lĩnh vực điều khiển Robot.

Sau đây xin giới thiệu với bạn đọc một bài toán cỡ trungbình trong số các bài toán điều khiển Robot.

Bài toán (Robot):Một Robot di chuyển trên một nền phẳngchia thành lưới toạ độ nguyên ABCD như Hình 1. Gốc toạ độ đặt tại điểm Ă0,0).Robot xuất phát từ điểm R(x0,y0), mặt hướng về phía cạnh BC gọi là hướng Bắc vàđi theo một chương trình lập sẵn.

Yêu cầu: Xácđịnh điểm kết thúc T(x1,y1) của Robot sau khi hoàn thành chương trình dichuyển.

Chương trình lậpsẵn cho Robot là một xâu kí tự bao gồm một dãy các lệnh dạng Cm, được gọi làlệnh đơn, hoặc (u)m, trong đó C là mộttrong các chữ cái Q, q, D hoặc d, m là một số tự nhiên, u là một lệnh phức đượctạo từ một dãy lệnh đơn hoặc lệnh phức. Các lệnh đơn có ý nghĩa như sau:

+ Dm: Tiến về phia trước m bước, mỗi bước là một lần di chuyển từ mộtđiểm đến điểm kế tiếp theo hướng nhìn của Robot.

+ dm: Lùi về phía sau m bước.

+ Qm: Quay người m lần, mỗi lần quay một góc 45 độ theo chiều kim đồnghồ.

+ qm: Quay người m lần, mỗi lần một góc 45 độ ngược chiều kim đồng hồ.

+ (u)m: thực hiện m lần dãy lệnh u.

Ta quy ước, nếum = 1 thì có thể không viết giá trị m. Nếu m = 0 thì đoạn lệnh tương ứng đặttrước m được bỏ qua.

Dữ liệu vào: Tệpvăn bảnROBOT.INP gồm 2 dòng.

+ Dòng thứ nhất: hai số tự nhiên x0 y0 cách nhau bởi dấu cách cho biếtvị trí xuất phát của Robot.

+ Dòng thứ hai: Chương trình điều khiển Robot.

Dữ liệu ra: Tệpvăn bản ROBOT.OUT gồm 1 dòng chứa hai số tự nhiên x1 y1cách nhau bởi dấu cáchcho biết vị trí kết thúc của Robot sau khi hoàn thành chương trình di chuyển.

Các giá trị x0và y0, x1 và y1 có thể đạt tới 60 nghìn. Chương trình của Robot có thể bao gồm250 kí tự. Trục tung AB chứa toạ độ dòng x, trục hoành AD chứa toạ độ cột y.

Thí dụ:

ROBOT.INP

5 10

(D50Q2D50q3d50qD100)10d2

ROBOT.OUT

5 8

Bài giải

Trước hết ta mở tệp văn bản ROBOT.INP để đọc dữ liệu vàocác biến x0, y0 chứa toạ độ vị trí xuất phát của Robot và biến xâu kí tự s chứachương trình điều khiển Robot. Chươngtrình s, theo đầu bài chính là một lệnh phức. Ta sử dụng kỹ thuật hai pha đểphân tích chương trình của Robot thành các dòng lệnh ghi trong một bảng như Hình2. Các bạn có thể tham khảo bài Kỹ thuật hai pha trong số 7/2000.

Pha 1. Thủ tục xử lý LenhPhuc sẽ gọithủ tục LenhDon nếu gặp lệnh đơn dạng Cm vàgọi đệ quy LenhPhuc nếu gặp lệnh dạng (u)m,trong đó C là một trong bốn chữcái D, d, Q hoặc q, u là một lệnhphức, m là một số tự nhiên.

Chương trình sử dụng các hằng sau đây:

const

DauTu = ['(','Q','q','D','d'];

ChuSo = ['0'..'9'];

MN = 250;

DauTu là hằng kiểu tập chứa các kí tự đầu mỗi lệnh, trongđó( là dấu hiệu đầu của một lệnh phức, bốn chữ cái còn lại là dấu hiệu đầucủa một lệnh đơn. MN cho biết chiều dàitối đa của chương trình điều khiển Robot tức là chiều dài tối đa của xâu kí tựs.

Thủ tục LenhPhuc sẽ đọc từng kí tự của s, nhận biết từngdạng lệnh đơn hay phức để tạo ra các dòng điều khiển tương ứng trong một bảng.

Bảng được tạo bởi 4 cột, mỗicột là một mảng:

Kt: array[0..MN] of char;

Tu: array[0..MN] of byte;

Lap: array[0..MN] of word;

Với mỗi dòng n của bảng,Kt[n] là kí tự điều khiển vận động của Robot, Lap[n] cho biết số lần lặp lạimột thao tác quay hoặc di chuyển, Nếu Kt[n]=* thì dòng n sẽ là một dòng lặpứng với một lệnh phức, khi đó Tu[n] cho biết dòng đầu tiên trong bảng của lệnhphức mà ta cần lặp. Sau khi xử lý dãy lệnh (D50Q2D50q3d50qD100)10 thủ tụcLenhPhuc sẽ sinh ra dòng 8 của bảng. Dòng này cho biết Robot cần lặp lại dãythao tác 10 lần kể từ dòng thứ nhất.

Biến ii kiểu byte dùng đểduyệt các kí tự của xâu s, biến n kiểu byte ghi nhận dòng mới phát sinh trongbảng. Các biến được khởi trị như sau:

ii := 1;

n := 0;

s := s +#;

Ta thêm cho s một kí tự lạ đểlàm dấu kết dòng và do đó sẽ đỡ phải kiểm tra giới hạn của chỉ dẫn ii.

Procedure LenhPhuc;

var g: byte;

while s[ii] in DauTu do

if s[ii] = '(' then

g := n;

inc(ii);

LenhPhuc;

if s[ii]=) then inc(n);

Kt[n] := '*';

Tu[n] := g+1;

Lap[n] := DocSo;

if Lap[n] = 0 then n := g

else if Lap[n] = 1 then dec(n);

end

else LenhDon;

end;

Thủ tục LenhDon xử lý các lệnh đơn dạng C hoặc Cm, trong đó C là mộttrong bốn chữ cái D, d, Q hoặc q, mlà một số tự nhiên. Thủ tục này tạo một dòng n cho bảng với hai giá trị: Kt[n]chứa kí tự điều khiển Robot và Lap[n]chứa số lần lặp của thao tác tương ứng.

procedure LenhDon;

inc(n);

Kt[n] := s[ii];

inc(ii);

Lap[n] := DocSo;

if Lap[n] = 0 then dec(n);

end;

Hàm DocSo đọc dãy chữ số trong s để tạo ra một số tựnhiên. Khi không gặp số, theo quy địnhcủa đầu bài ta gán DocSo = 1.

function DocSo: word;

var m: word;

DocSo := 1;

if not (s[ii] in ChuSo) then exit;

m := 0;

while s[ii] in ChuSo do

m := m*10 + ord(s[ii]) - ord('0');

inc(ii);

end;

DocSo := m;

end;

Pha 1 sẽ đươc gọi thông quathủ tục TaoBang như sau:

procedure TaoBang;

s := s + '#';

ii := 1;

n := 0;

LenhPhuc;

end;

Pha 2. Thủ tục DiChuyen trong phanày điều khiển Robot di chuyển theo từng dòng của bảng đã tạo lập ở pha thứnhất. Với mỗi dòng i=1..n ta xét các trường hợp:

* Nếu Kt[i] là một trong hai chữ cái Q hoặc q tacho Robot xoay người Lap[i] lần theo chiều kim đồng hồ, nếu Kt[i]=Q, hoặcngược chiều kim đồng hồ, nếu Kt[i]=q. Để làm việc này ta dùng biến nguyênHuong cho biết mặt của Robot hướng về phía nào. Tính theo chiều kim đồng hồ ta có8 hướng là 0: Bắc, 1: Đông-Bắc, 2: Đông, 3: Đông-Nam, 4: Nam, 5: Tây-Nam, 6:Tây, 7: Tây-Bắc. Mỗi lần Robot xoay mình, mặt của nó sẽ chuyển đi một hướng,vậy sau khi xoay Lap[i] lần thì hướng của Robot sẽ được tính như sau:

Huong:=(Huong+(Lap[i]mod 8)) mod 8.

Tươngtự ta có thể lập công thức tính hướng cho trường hợp Kt[i]=q:

Huong:=(Huong-(Lap[i]mod 8));

if Huong<0 then Huong:=8+Huong;

* Nếu Kt[i] là một trong hai chữ cái D hoặc d tasẽ tính lại toạ độ x1, y1 của Robot sau khi cho Robot di chuyển Lap[i] bước vềphía trước nếu Kt[i] =D hoặc về phia sau nếu Kt[i] =d. Ta dùng hai mảngdx và dy gán trước giá trị cần di chuyển của Robot theo hướng:

const

dx: array[0..7] of integer = (1,1,0,-1,-1,-1,0,1 );

dy: array[0..7] of integer = (0,1,1,1 ,0 ,-1,-1,-1);

Tathấy dx[h] cho biết Robot cần thay đổi tung độ x1 mỗi khi bước một bước theohướng h, cụ thể là:

- giữnguyên toạ độ dòng, dx[h]=0,

- tăngtoạ độ dòng thêm 1, dx[h]=1 hoặc

- giảmtoạ độ dòng đi 1, d[x]=-1

tuỳtheo giá trị của hướng. Tương tự, giá trị dy[h] cho biết sự thay đổi hoành độy1. Thí dụ: Nếu Robot đang đứng tại toạ độ x1=5, y1=10, mặt quay về hướngĐông-Nam (h=3) thì sau khi di chuyển 1 bước (theo lệnh đơn D) về phía trướcRobot sẽ chuyển sang toạ độ:

x1 =x1+dx[h] = 5+dx[3] = 5-1 =4

y1 =y1+dy[h] = 10+1 = 11

Vậy công thức tính toạ độ choRobot khi di chuyển Lap[i] bước theo hướng mắt nhìn là:

x1:=x1+dx[Huong]*Lap[i];

y1:=y1+dy[Huong]*Lap[i];

và ngược hướng mắt nhìn là:

x1:=x1-dx[Huong]*Lap[i];

y1:=y1-dy[Huong]*Lap[i];

Để quản lý các dòng lặp ta sửdụng một mảng Dem, Dem[i] cho biết số lần lặp một lệnh phức. Khi Dem[i] < Lap[i] ta đặt i := Tu[i] để Robot lặp lại dãy thao tác tính từ dòng i. Khi Dem[i] = Lap[i] ta đặt lại giá trị của con đếm Dem[i] := 0 rồi chuyển qua dòng điều khiển mới, i+1. Thủ tục DiChuyen khi đó sẽ như sau:

procedure DiChuyen;

var i: byte;

Huong := 0;

x1 := x0; y1 := y0;

for i := 1 to n do Dem[i] := 0;

i := 1;

while i <= n do

if Kt[i] = '*' then

inc(Dem[i]);

if Dem[i] < Lap[i] then i := Tu[i]

else

Dem[i] := 0;

inc(i);

end;

end

else

case Kt[i] of

'Q': Huong := (Huong + (Lap[i] mod 8)) mod 8;

'q': begin Huong := (Huong - (Lap[i] mod 8));

if Huong < 0 then Huong := 8 + Huong;

end;

'D': begin x1 := x1 + dx[Huong]*Lap[i];

y1 := y1 + dy[Huong]*Lap[i];

end;

'd': begin x1 := x1 - dx[Huong]*Lap[i];

y1 := y1 - dy[Huong]*lap[i];

end;

end;{case}

inc(i);

end;

end;

end;

Bài tập. Biết vị trí xuất phát R(x0,y0) và vị trí kếtthúc T(x1,y1). Hãy viết chương trình ngắn nhất để điều khiển Robot đi từ R đếnT. Chiều dài của chương trình được đo bằng tổng số lần thực hiện một thao táccơ sở Q, q, D hoặc d.

Nguyễn Xuân Huy