Dạo này thấy box Pascal ỉu xìu quá!

**truongngocdai** · 12-02-2007 16:07

Dạo này thấy box Pascal ỉu xìu quá! Em đành phải đưa ra ý kiến để làm nóng nó lên vậy. Theo em, mọi người nên tổ chức 1 cuộc thi Pascal: Các đề được đưa ra và đợi mọi người post lên lời giải (có code .pas đính kèm + thuật toán). Mọi người thấy ý kiến của em thế nào? Em xin mở hàng = bài toán đầu tiên:

Robot đi tuần
Một con robot phải đi tuần trên một khu vực hình chữ nhật gồm m × n ô (m dòng, n cột). Các dòng được đánh số từ 1 đến m, các cột được đánh số từ 1 đến n. Ô (i, j) thể hiện ô ở dòng i và cột j. Mỗi bước, robot có thể di chuyển đến một trong bốn ô kề cạnh, ví dụ từ ô (x, y) có thể đến được (x + 1, y), (x – 1, y), (x, y + 1) và (x, y – 1). Một vài ô có chứa những chướng ngại vật. Để đi vào những ô này, robot phải chuyển sang chế độ turbo. Vì vậy, robot này không thể di chuyển liên tục qua nhiều hơn k ô có chứa chướng ngại vật. Bạn cần viết chương trình tìm đường đi ngắn nhất từ (1, 1) đến (m, n) biết rằng cả hai ô (1, 1) và (m, n) không có chướng ngại vật.
Input: Bao gồm một vài bộ test. Dòng đầu tiên của input ghi một số nguyên dương không lớn hơn 20 là số bộ test. Các dòng tiếp theo mô tả các bộ test. Với mỗi bộ test, dòng đầu tiên chứa hai số m và n (1 ≤ m, n ≤ 20). Dòng thứ hai chứa số nguyên k (0 ≤ k ≤ 20). Dòng thứ i trong m dòng tiếp theo chứa n số aij (i = 1, 2, … m, j = 1, 2,.. n). Giá trị của aij = 1 nếu có chướng ngại vật ở ô (i, j) và bằng 0 nếu ngược lại.
Output: Với mỗi bộ test, nếu tồn tại một đường đi cho robot, viết ra số nguyên s là số bước di chuyển ít nhất. Nếu không tồn tại đường đi, in ra -1.

Test mẫu:

**F12** · 12-02-2007 22:50

Hoan hô ý kiến rất thú vị của bạn truongngocdai.

Rất mong mọi người ủng hộ ý kiến này. Đây là một cơ hội luyện khả năng code chuẩn.

Vậy làm sao để mọi người biết code của mình là đúng. Bạn sẽ là người tạo test và làm check phải không ?

**truongngocdai** · 13-02-2007 13:41

các bạn có thể tự check trước và Message cho mình, không nên đưa code lên TOPICS để tránh người sau rút kinh nghiệm của người trước

. Đương nhiên là khi nào có người làm code đúng thì ngay lập tức một bài khác sẽ được giao.

**thuonghcm** · 13-02-2007 21:06

vậy mail của bác Trương Ngọc Đại đâu? mà bác nói...là...
"Ngay lập tức 1 bài khác sẽ được giao là sao?", chắc là
sẽ ra 1 đề khác rồi"cho bài giải vừa rồi" vào bí mật luôn hả?

**truongngocdai** · 13-02-2007 21:54

bạn nào test thấy code của mình đã chuẩn thì có thể post lên topics luôn, (ko post lên code chưa hoàn chỉnh hoặc thuật toán). Hiện tại mình đã nhận được bài giải của: F12

Đây là code của F12

Code:

program robot;

const
  fi = 'robot.inp';
  fo = 'robot.out';
  maxn = 20;
  gd : array[1..4] of integer = (-1,0,1,0);
  gc : array[1..4] of integer = (0,1,0,-1);

var
  f,g                 : text;
  m,n,h               : integer;
  a                   : array[1..maxn,1..maxn] of byte;
  c                   : array[1..maxn,1..maxn,0..20] of integer;
  queue               : array[1..9000,1..3] of byte;
  first,last,result   : integer;

procedure khoitao;
begin
  fillchar(a,sizeof(a),0);
  fillchar(c,sizeof(c),0);
  fillchar(queue,sizeof(queue),0);
  result:=0;
end;

procedure doc;
var i,j:integer;
begin
  readln(f,m,n);
  readln(f,h);
  for i := 1 to m do
    begin
      for j := 1 to n do read(f,a[i,j]);
      readln(f);
    end;
end;

procedure lam;
var i,j,p,q,ii,jj,k:integer;
begin
  queue[1,1]:=1;
  queue[1,2]:=1;
  queue[1,3]:=0;
  first:=1;
  last:=1;
  c[1,1,0]:=1;
  while first<=last do
    begin
      i:=queue[first,1];
      j:=queue[first,2];
      p:=queue[first,3];
      inc(first);
      for k := 1 to 4 do
        begin
          ii:=i+gd[k];
          jj:=j+gc[k];
          if (ii>0) and (jj>0) and (ii<=m) and (jj<=n) then
            begin
              if a[ii,jj]=1 then q:=p+1 else q:=0;
              if (q<=h) and (c[ii,jj,q]=0) then
                begin
                  c[ii,jj,q]:=c[i,j,p]+1;
                  inc(last);
                  queue[last,1]:=ii;
                  queue[last,2]:=jj;
                  queue[last,3]:=q;
                end;
            end;
        end;
    end;
  result:=maxint;
  for i := 0 to h do
    if (c[m,n,i]>0) and (result>c[m,n,i]) then result:=c[m,n,i];
  if result=maxint then result:=-1 else dec(result);
end;

procedure viet;
begin
  writeln(g,result);
end;

procedure mofile;
begin
  assign(f,fi); reset(f);
  assign(g,fo); rewrite(g);
end;

procedure dongfile;
begin
  close(f);
  close(g);
end;

var test,testcase:integer;
begin
  mofile;
  readln(f,test);
  for testcase:=1 to test do
    begin
      khoitao;
      doc;
      lam;
      viet;
    end;
  dongfile;
end.

Mình có đôi chút nhận xét về bài của F12:
- Bạn lưu trữ dữ liệu vào 1 mảng 3 chiều ? Ko nên vậy! Chỉ cần đọc vào từng ma trận rồi làm luôn rồi tiếp tục ma trận sau ...
- Có thể bạn nên sử dụng các kiểu dữ liệu "tự chế" thì đỡ tốn hơn

Mong các bạn đóng góp ý kiến cho bài giải của F12

P/S: Bài giải này sẽ là tối ưu nhất nếu như trong 1 tuần tới ko có bài giải nào tốt hơn

**truongngocdai** · 13-02-2007 22:20

À, mình có ý kiến. Bài giải tốt nhất là bài giải mà trong 1 tuần kể từ khi bài đó được post, ko có bài giải nào tối ưu hơn (về các mặt tốc độ, ko gian lưu trữ,...). Có thể giải thưởng là:
- 1 yêu cầu nào đó về IT (Software, *****, Programming, Designing,...)
- 1 chầu kem OFFLINE với người nào đoạt giải 2 lần liên tiếp
*****Ưu tiên cho những người có nêu thuật toán. Giả sử một người nêu code, 1 người nêu thuật toán thì ưu tiên cho người nêu code

Nếu trước và trong ngày 20/2/2007 ko có bài giải nào tối ưu hơn bài giải của bạn thì bạn F12 là "người chiến thắng"