Thuật toán loang (Bài toán thỏ và cà rốt)!

[nguyentaingoc]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Các bạn suy nghĩ giải bài toán này nhé
Cho một bản đồ số gồm số 1 và 0 (input) . số 1 là đường đi 0 là bờ ( ko đi) được
Con thỏ đang đứng ở vị trí 1,1. Nhập từ bàn phím vị trí của cà rốt và mang giá trị là
số 2.
a)Hãy lập chương trình xem thử từ vĩ trí ban đầu con thỏ có đến được vị trí ca rot không?
b)Nếu được tính số bước ít nhất để đến
VD:
1 1 1 1 0 1 1
0 1 0 1 0 1 0
1 0 1 1 1 2 1
0 0 0 1 0 0 0
0 1 1 0 1 1 1
TL a) có
b) 7

 

[concanhcam]

uses crt;
const inp='loang.inp';   outp= 'loang.out';


var a:array[1..100,1..100] of byte;
    i,j,dem,max,m,n:byte;
    kt:boolean;

    fo,fi:text;
procedure   nhap;
    begin
        assign(fi,inp);
        reset(fi);
           read(fi,n,m );
           for i:=1 to n do
              for j := 1 to m do
                 read(fi,a[i,j]);
        close(fi);
             assign(fo,outp);
     rewrite(fo);

    end;
procedure loang(x,y:byte);
   begin
     if a[x,y] =2 then
       begin
         write (fo,' co  the an ca rot ');
         kt:=true;
       end;

     if a[x,y] = 1 then
       begin
         dem :=dem+1;
         a[x,y]:=0;
         if  x>1 then loang(x-1,y);
         if  y>1 then loang(x,y-1);
         if  x<n then loang(x+1,y);
         if  y<m then loang(x,y+1);
       end;
   end;
procedure xuli;
   begin
       loang(1,1);
       if not kt then
          write (fo, ' khong the an ca rot');


   end;
procedure xuat;
   begin
        close(fo);
   end;
begin
   nhap;
   xuli;
   xuat;
end.

câu A

 

[getahead]

Sử dụng loang bằng BFS cũng được bạn cho nó nhanh.