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
2018-01-12 15:01:26
code ac : cpp.sh/5ot6e
2017-11-15 16:07:15
kham khảo code:
https://vietcodes.github.io/code/113/
2017-09-10 04:30:26
không đi được vào đá
@phanduy16
2017-08-17 20:13:36 Con Bò Huyền Thoại
https://kienthuc24h.com/vmunch-spoj-2722-gam-co/
2016-05-17 12:32:59
vãi BFS ghi sai 2 chữ cũng vẫn dc 30 @@@
sửa lại đã AC :v
2015-09-18 16:43:08
cai nay ae can than! hinh nhu tinh ca o cuoi ms dc@@ k +1 dc 0 mak +1 dc 20 @@
2015-09-18 14:43:31
queue+loang
2015-09-15 10:23:23 Khanh Ninh
Code BFS bang Stack =]]]]]
2015-07-26 16:57:23 N�ng D�n John
@Bee: dạ vì BFS tìm đường đi ngắn nhất ạ!
2015-07-18 08:48:19 Bee
tại sao BFS mới được mà DFS không được ???
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.