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.|

BCMUNCH - Gặm cỏ

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


ID RESULT TIME
code...



Được gửi lên bởi:adm
Ngày:2011-11-02
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA
Nguồn bài:USACO

hide comments
2015-03-26 17:55:48 Con Bò Huyền Thoại
http://kienthuc24h.com/vmunch-spoj-2722-gam-co/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.