Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

 Hái Nấm (MUSHROOM)

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
cotendn
Gà mờ


Tổng số bài gửi : 1
Join date : 26/02/2012

Bài gửiTiêu đề: Hái Nấm (MUSHROOM)   Sun 26 Feb 2012, 10:01

Mọi người xem hộ bài này mình làm sai chỗ nào nhá

HÁI NẤM
Một cháu gái được mẹ giao nhiệm vụ hàng ngày đến thăm bà nội.Từ nha mình đến nhà bà nội cô bé phải đi qua một khu rừng có rất nhiều nấm, có 3 loại nấm ăn được cô bé đánh số là 1,2,3. Mỗi lần đến thăm bà, cô bé hái ít nhất là 2 loại nấm. Khu rừng cô bé đi qua được chia thành lưới ô vuông m hàng và n cột,
các hàng được đánh số từ trên xuống, bắt đầu từ 1, các cột được đánh số từ trái sang phải bắt đầu từ 1, ô nằm giao của hàng i cột j có tọa độ (i,j). Trên mỗi ô vuông, trừ ô (1,1) và ô (m,n), các ô còn lại hoặc có nấm độc cô bé không dám đi vào (đánh dâu là -1) hoặc có đúng 1 loại nấm có thể ăn được (đánh dấu bằng số hiệu loại nấm đó), khi đi đến ô nào, cô bé hái loại nấm có ở ô đó.Xuất phát từ ô (1,1), để đến ô (m,n), cô bé luôn đi sang phải hoặc xuống dưới.
Mỗi ngày cô bé đi theo một con đường khác nhau( hai con đường khác nhau nếu chúng khác nhau ở ít nhất một ô)
Yêu cầu: cho bảng mxn ô vuông mô tả trạng thái khu rừng. Gọi k là số con đường khác nhau để cô bé đến thăm bà nội theo cách chọn đường đi ở trên. Tính k mod 10^7.
Dữ liệu: vào từ file MUSHROOM.INP
Dòng đấu chứa 2 số m,n (1<m,n<101);
m dòng tiếp theo, mỗi dòng chứa n số nguyên cho biết thông tin về khu rừng , riêng ở ô (1,1) và (m,n) luôn luôn bằng 0, các ô còn lại có giá trị -1 hoặc 1 hoặc 2 hoặc 3.
Ví dụ
MUSHROOM.INP
3 4
0 3 -1 2
3 3 3 3
3 1 3 0

MUSHROOM.OUT
3
Code:
const fi='hainam.INP';
      fo='hainam.OUT';
var f:text;
    a,b1,b2:array[0..101,0..101] of integer;
    d:array[1..101,1..101] of boolean;
    i,j,m,n:integer;
procedure qhd; // số đường đi từ ô (1,1) đến ô (i,j)
begin
  fillchar(b1,sizeof(b1),0);
  for i:=1 to m do
    for j:=1 to n do
    if a[i,j] <>-1 then begin
      b1[i,j]:=b1[i-1,j]+b1[i,j-1];
      b1[1,1]:=1;
    end;
end;
procedure danhdau; //đánh dấu xem có đi qua các loại nấm khác nhau không
begin
  for i:=1 to m do
    for j:=1 to n do
      if ((a[i,j]<>a[i-1,j]) and (a[i-1,j]<>0))
      or ((a[i,j]<>a[i,j-1]) and (a[i,j-1]<>0))
        then d[i,j]:=true
      else d[i,j]:=false;
end;
procedure kq; // số đường đi thỏa mãn đề bài
begin
  for i:=1 to m do
    for j:=1 to n do
      if d[i,j]=true then b2[i,j]:=b2[i-1,j] + b2[i,j-1]
      else b2[i,j]:=b1[i,j];
  write(f,b2[m,n]);
end;
begin
  assign(f,fi);reset(f);
  read(f,m,n);
  readln(f);
  for i:=1 to m do
    for j:=1 to n do read(f,a[i,j]);
  close(f);
  assign(f,fo);rewrite(f);
  qhd;
  danhdau;
  kq;
  close(f);
end.
Về Đầu Trang Go down
 
Hái Nấm (MUSHROOM)
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Lớp chuyên tin-
Chuyển đến