cotendn Gà mờ
Tổng số bài gửi : 1 Join date : 26/02/2012
| Tiê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. | |
|