Đề Bài HSG: Đường đi trong lưới có rào cản và chi phí tối thiểu

Mô Tả:

Cho một lưới có kích thước ~m \times n~ (~m~ dòng và ~n~ cột). Bạn bắt đầu từ góc trên bên trái (tọa độ ~(0, 0)~) và muốn di chuyển đến góc dưới bên phải (tọa độ ~(m-1, n-1)~).

• Bạn có thể di chuyển sang phải hoặc xuống dưới tại mỗi bước.
• Trong lưới có một số ô bị rào cản (ô có giá trị là ~1~), và có một số ô có chi phí di chuyển khác nhau (ô có giá trị từ ~0~ đến một số nguyên dương).

Bạn cần tìm ra số cách để di chuyển từ góc trên bên trái đến góc dưới bên phải sao cho chi phí tổng thể thấp nhất.

Input:

• Một ma trận ~m \times n~ với các giá trị:
  • Giá trị ~0~ (ô trống) có thể di chuyển qua.
  • Giá trị ~1~ (rào cản) không thể di chuyển qua.
  • Giá trị khác ~0~ biểu thị chi phí di chuyển qua ô đó.

Bạn cần tính tổng chi phí thấp nhất và số cách có thể di chuyển từ góc trên bên trái đến góc dưới bên phải.

Output:

• Nếu có ít nhất một cách di chuyển, in ra chi phí thấp nhất và số cách di chuyển có chi phí thấp nhất.
• Nếu không có cách nào di chuyển (vì toàn bộ đường bị rào cản), in ra -1.

Ví Dụ:

Input:

3 3
0 2 0
1 1 0
0 1 0

Output:

2 1

Giải thích: Có 1 cách di chuyển có chi phí thấp nhất là đi qua các ô ~(0,0) -> (1,2) -> (2,2)~, với chi phí là ~2~.

Phương Pháp Giải Quyết:

1. Dùng Quy Hoạch Động:

   • Tạo bảng DP với hai giá trị: một cho chi phí tối thiểu và một cho số cách di chuyển đến ô đó với chi phí tối thiểu.
   • Chi phí của ô dp[i][j] sẽ là chi phí tối thiểu từ góc trên bên trái (0,0) đến ô đó, với công thức: dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] (Với grid[i][j] là chi phí của ô tại (i, j)).
   • Số cách di chuyển đến ô đó là tổng số cách từ ô bên trên và ô bên trái: ways[i][j] = ways[i-1][j] + ways[i][j-1]

2. Điều kiện biên: Các ô bị rào cản không thể di chuyển qua, do đó phải có điều kiện xử lý khi gặp ô rào cản.

In ra dãy nhị phân có độ dài ~n~

ví dụ ~n=3~ thì in ra ~000,001,010, 011,100,101,110,111~

const ip='bt.inp';
      op='bt.out';
var n:byte;
    f:text;
    x:array[1..100] of byte;

    procedure try(i:integer);
    var k:byte;
        v:integer;
    begin
         for v:=0 to 1 do
         begin
              x[i]:=v;
              if i=n then
              begin
                   for k:=1 to n do write(f,x[k]);
                   writeln(f);
              end
              else try(i+1);
         end;
    end;

BEGIN
     assign(f,ip);
     reset(f);
     readln(f,n);
     close(f);
     assign(f,op);
     rewrite(f);
     try(1);
     close(f);
END.