Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Bài 2. HÁI NẤM

Một cháu gái hàng ngày được mẹ giao nhiệm vụ đến thăm bà nội. Từ nhà mình đến nhà bà nội cô bé 

phải đi qua một khu rừng có rất nhiều loại nấm. Trong số các loại nấm, có ba loại có thể ăn được. Cô 

bé đánh số ba loại nấm ăn được lần lượt là 1, 2 và 3. Là một người cháu  hiếu thảo cho nên cô bé 

quyết định mỗi lần đến thăm bà, cô sẽ hái ít nhất hai loại nấm ăn được để nấu súp cho bà. Khu rừng 

mà cô bé đi qua được chia thành lưới ô vuông gồm m hàng và n cột. Các hàng của lưới được đánh số

từ trên xuống dưới bắt đầu từ 1, còn các cột – đánh số từ trái sang phải, bắt đầu từ 1. Ô nằm giao của 

hàng  i  và 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 và  cô bé không dám  đi vào (đánh dấu là  -1), hoặc  là có đúng một loại nấm có thể ăn được 

(đánh dấu bằng số hiệu của loại nấm đó). Khi cô bé đi vào một ô vuông có nấm ăn được thì cô bé sẽ 

hái loại nấm mọc trên ô đó. Xuất phát từ ô (1,1), để đến được nhà bà nội ở ô (m, n) một cách nhanh 

nhất cô bé luôn đi theo hướng sang phải hoặc xuống dưới.

Việc đi thăm bà và hái nấm trong rừng sâu gặp nguy hiểm bởi có một con cho sói luôn theo dõi và 

muốn ăn thịt cô bé. Để phòng tránh chó sói theo dõi và ăn thịt, cô bé quyết định mỗi ngày sẽ đ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 m×n  ô  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 đã nêu ở trên. Hãy tính giá trị k  mod 10

7

.

Dữ liệu: Vào từ file văn bản MUSHROOM.INP:

-  Dòng đầu chứa 2 số m, n (1 < m, n <101),

-  m  dòng tiếp tiếp theo, mỗi dòng chứa  n  số  nguyên cho biết thông tin về  các ô của khu rừng.

(riêng giá trị ở hai ô (1,1) và ô (m, n) luôn luôn bằng 0 các ô còn lại có giá trị bằng -1, hoặc

1, hoặc 2, hoặc 3).

Hai số liên tiếp  trên một dòng cách nhau một dấu cách.

Kết quả: Đưa ra file văn bản MUSHROOM.OUT chứa một dòng ghi một số nguyên k mod 10

7

.

Ví dụ: 

MUSHROOM.INP    MUSHROOM.OUT

3 4   

0 3 -1 2

3 3 3 3

3 1  3 0

3

Lưu ý: Có 60% số test với M, N không quá 10. Giải đúng các test này, thí sinh được không ít hơn 

60% số điểm tối đa cho toàn bộ bài t
 
Một cháu gái hàng ngày được mẹ giao nhiệm vụ đến thăm bà nội. Từ nhà mình đến nhà bà nội cô bé phải đi qua một khu rừng có rất nhiều loại nấm. Trong số các loại nấm, có ba loại có thể ăn được. Cô bé đánh số ba loại nấm ăn được lần lượt là 1, 2 và 3. Là một người cháu  hiếu thảo cho nên cô bé quyết định mỗi lần đến thăm bà, cô sẽ hái ít nhất hai loại nấm ăn được để nấu súp cho bà. Khu rừng mà cô bé đi qua được chia thành lưới ô vuông gồm m hàng và n cột. Các hàng của lưới được đánh số từ trên xuống dưới bắt đầu từ 1, còn các cột – đánh số từ trái sang phải, bắt đầu từ 1. Ô nằm giao của hàng  i  và 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 và  cô bé không dám  đi vào (đánh dấu là  -1), hoặc  là có đúng một loại nấm có thể ăn được (đánh dấu bằng số hiệu của loại nấm đó). Khi cô bé đi vào một ô vuông có nấm ăn được thì cô bé sẽ hái loại nấm mọc trên ô đó. Xuất phát từ ô (1,1), để đến được nhà bà nội ở ô (m, n) một cách nhanh nhất cô bé luôn đi theo hướng sang phải hoặc xuống dưới.
Việc đi thăm bà và hái nấm trong rừng sâu gặp nguy hiểm bởi có một con cho sói luôn theo dõi và 
muốn ăn thịt cô bé. Để phòng tránh chó sói theo dõi và ăn thịt, cô bé quyết định mỗi ngày sẽ đ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 m×n  ô  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 đã nêu ở trên. Hãy tính giá trị k  mod 10^7.

Dữ liệu: Vào từ file văn bản MUSHROOM.INP:
-  Dòng đầu chứa 2 số m, n (1 < m, n <101),
-  m  dòng tiếp tiếp theo, mỗi dòng chứa  n  số  nguyên cho biết thông tin về  các ô của khu rừng. (riêng giá trị ở hai ô (1,1) và ô (m, n) luôn luôn bằng 0 các ô còn lại có giá trị bằng -1, hoặc 1, hoặc 2, hoặc 3). Hai số liên tiếp  trên một dòng cách nhau một dấu cách.
Kết quả: Đưa ra file văn bản MUSHROOM.OUT chứa một dòng ghi một số nguyên k mod 10^7.
Ví dụ: 
MUSHROOM.INP    
3 4   
0 3 -1 2
3 3 3 3
3 1  3 0
MUSHROOM.OUT
3