Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VMUNCH - Gặm cỏ

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vmunch


Bessie rất yêu bãi cỏ của mình và thích thú chạy về chuồng bò vào giờ vắt sữa buổi tối.

Bessie đã chia đồng cỏ của mình là 1 vùng hình chữ nhật thành các ô vuông nhỏ với R (1 <= R <= 100) hàng và C (1 <= C <= 100) cột, đồng thời đánh dấu chỗ nào là cỏ và chỗ nào là đá. Bessie đứng ở vị trí R_b,C_b và muốn ăn cỏ theo cách của mình, từng ô vuông một và trở về chuồng ở ô 1,1 ; bên cạnh đó đường đi này phải là ngắn nhất.

Bessie có thể đi từ 1 ô vuông sang 4 ô vuông khác kề cạnh.

Dưới đây là một bản đồ ví dụ [với đá ('*'), cỏ ('.'), chuồng bò ('B'), và Bessie ('C') ở hàng 5, cột 6] và một bản đồ cho biết hành trình tối ưu của Bessie, đường đi được dánh dấu bằng chữ ‘m’.

           Bản đồ               Đường đi tối ưu
        1 2 3 4 5 6  <-cột      1 2 3 4 5 6  <-cột
      1 B . . . * .           1 B m m m * .
      2 . . * . . .           2 . . * m m m
      3 . * * . * .           3 . * * . * m
      4 . . * * * .           4 . . * * * m
      5 * . . * . C           5 * . . * . m

Bessie ăn được 9 ô cỏ.

Cho bản đồ, hãy tính xem có bao nhiêu ô cỏ mà Bessie sẽ ăn được trên con đường ngắn nhất trở về chuồng (tất nhiên trong chuồng không có cỏ đâu nên đừng có tính nhé)

Dữ liệu

  • Dòng 1: 2 số nguyên cách nhau bởi dấu cách: R và C
  • Dòng 2..R+1: Dòng i+1 mô tả dòng i với C ký tự (và không có dấu cách) như đã nói ở trên.

Kết quả

  • Dòng 1: Một số nguyên là số ô cỏ mà Bessie ăn được trên hành trình ngắn nhất trở về chuồng.

Ví dụ

Dữ liệu
5 6
B...*.
..*...
.**.*.
..***.
*..*.C

Kết quả
9

Được gửi lên bởi:Jimmy
Ngày:2008-05-24
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:USACO US-Open 2008 - Bảng Đồng

hide comments
2015-05-25 04:45:39 Tran ngoc
lỗi edit run là sao các bạn
2015-03-29 07:25:09 Hồ Nguyễn Hải Tuấn
vậy ô có đá thì mình có thể đi qua ko nhỉ
2015-02-17 05:21:56 Bee
nói chung về tới chuồng mà ăn càng ít là ok.
2014-12-01 16:35:54 Change The World
1 đấm AC =))
2014-10-24 13:51:58 Phạm Mạnh Hưng
Test ảo nhé hee, 80% c >= r
2014-10-21 15:37:53 Virus
Em loang bình thường và vô cùng bình thường, và em ko hiểu tại sao 10đ/9 lần chấm...
Em muốn đập máy vì không tìm được lỗi sai
2014-10-08 16:53:52 Nguyễn Ðức Linh
cái này quay lui thì sao hả m.n?
2014-10-05 15:31:14 Anh Quân
Bài này làm theo thuật toán nào vậy mọi người?
2014-10-05 15:28:29 Anh Quân
Bai Nay lam theo thuat toan gi vay moi nguoi?
2014-08-18 19:04:23 Saitama
tại sao mình đc 10 điểm mà trong hồ sơ lại ghi đạt yc thế nhỉ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.