Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCROBOT/
1. Đề bài BCROBOT spoj
Bạn vừa tạo ra một bảng để cho rô-bốt có thể tìm đường đi từ ô ở trên cùng – bên trái (ô xuất phát) đến ô ở dưới cùng – bên phải (ô đích). Tuy nhiên, do quên mất một số skill AI mà bạn chỉ lập trình cho rô-bốt có thể đi sang phải 1 ô hoặc xuống dưới 1 ô. Bạn đặt một số chướng ngại vật trên các ô của bảng (dĩ nhiên là rô-bốt ko thể đi vào các ô này), sau đó bạn ngồi quan sát. Tuy nhiên, sau một thời gian, bạn cảm thấy mệt mỏi vì nó bị mắc kẹt và bạn tự hỏi: “Có bao nhiêu đường đi có thể cho rô-bốt từ ô xuất phát tới ô đích” và “Nếu không có, thì liệu rô-bốt có thể đến ô đích nếu nó được lập trình có thể đi lên trên 1 ô và sang trái 1 ô”.
Vì vậy, bạn quyết định viết 1 chương trình, cho kích thước của bảng n×n với các chướng ngại vật đã được dánh dấu mà rô-bốt không thể đi tới. Đếm số đường đi khác nhau mà rô-bốt có thể đi từ ô xuất phát tới ô đích. Và nếu không có đường đi, bạn phải kiếm tra xem có thể đi từ ô xuất phát tới ô đích nếu có thể sang trái và lên trên. Tuy nhiên, chương trình của bạn không xử lý các số rất lớn, do đó, kết quả phải được lấy dư cho 2^31-1.
Dữ liệu:
Dòng đầu tiên chứa một số nguyên n (1 <= n <= 1000).
N dòng sau, mỗi dòng chứa n kí tự đại, mỗi kí tự diện cho một ô của bảng. Kí tự có thể là ‘.’ hoặc ‘#’. Kí tự ‘.’ nếu ô đó có thể đi, hoặc ‘#’ nếu ô đó là chướng ngại vật. Không có trường hợp có chướng ngại vật ở ô xuất phát và ô đích.
Kết quả:
In ra một dòng chứa số nguyên là số đường đi khác nhau từ ô xuất phát tới ô kết thúc (lấy dư cho 2^31-1) hoặc “THE GAME IS A LIE” nếu không thể đi từ ô xuất phát tới ô kết thúc bằng cách chỉ sang phải và xuống dưới nhưng có thể đi nếu chấp nhận thêm cách đi lên trên và sang trái, hoặc INCONCEIVABLE nếu đơn giản là không có đường đi từ ô xuất phát tới ô đích.
Ví dụ:
| INPUT | OUTPUT |
| 5….. #..#. #..#. …#. ….. | 6 |
| INPUT | OUTPUT |
| 7……# ####… .#….. .#…#. .#….. .#..### .#….. | THE GAME IS A LIE |
2. Hướng dẫn BCROBOT spoj PTIT – Đường đi rô-bốt
– Dễ dàng nhận thấy đây là bài QHĐ cơ bản, có kết hợp với 1 xíu đồ thị để giải ý thứ 2
– Đầu tiên các bạn xây dựng mảng QHĐ với F[i,j] là số cách đi khi bước đến ô đó.
– Nếu A[i,j] = ‘.’ thì F[i,j]=F[i-1,j]+F[i,j-1]. ngược lại F[i,j]=0
– Nếu F[n,n] (tức là ô đích) =0 thì lúc này mình dùng BFS kiểm tra xem có đường đi từ ô 1,1 đến ô n,n bằng cách đi theo 4 hướng không, nếu có thì ghi ra “THE GAME IS A LIE” ngược lại “INCONCEIVABLE”.
3. Code tham khảo BCROBOT spoj PTIT – Đường đi rô-bốt
const fi='';
nmax=1005;
base=2147483647;
cld:array[1..4] of shortint=(0,0,1,-1);
clc:array[1..4] of shortint=(1,-1,0,0);
type data=longint;
var
f:text;
A:array[0..nmax+1,0..nmax+1] of char;
n:data;
B:array[0..nmax+1,0..nmax+1] of int64;
Qx,Qy:array[0..nmax*nmax+1] of data;
dau,cuoi:data;
free:array[0..nmax+1,0..nmax+1] of boolean;
procedure docfile;
var i,j:data;
begin
assign(f,fi); reset(f);
readln(f,n);
fillchar(a,sizeof(a),'#');
for i:=1 to n do
begin
for j:=1 to n do
read(f,a[i,j]);
readln(f);
end;
close(f);
end;
procedure QHD;
var i,j:data;
begin
fillchar(b,sizeof(b),0);
b[0,1]:=1;
for i:=1 to n do
for j:=1 to n do
if a[i,j]='.' then
B[i,j]:=(b[i-1,j]+b[i,j-1]) mod base;
end;
procedure them(x,y:data);
begin
inc(cuoi);
qx[cuoi]:=x;
qy[cuoi]:=y;
end;
procedure lay(var x,y:data);
begin
x:=qx[dau];
y:=qy[dau];
inc(dau);
end;
procedure BFS;
var i,j,u,v,x,y:data;
begin
dau:=1; cuoi:=0;
fillchar(free, sizeof(free),true);
them(1,1);
free[1,1]:=false;
while dau<=cuoi do
begin
lay(x,y);
for i:=1 to 4 do
begin
u:=x+cld[i];
v:=y+clc[i];
if (a[u,v]='.') and free[u,v] then
begin
free[u,v]:=false;
them(u,v);
end;
end;
end;
end;
procedure xl;
var i,j:data;
begin
bfs;
if free[n,n] then
writeln('INCONCEIVABLE')
else
writeln('THE GAME IS A LIE');
end;
begin
docfile;
qhd;
if B[n,n]>0 then
writeln(b[n,n])
else
xl;
end.
