Gặm cỏ

View as PDF

Submit solution


Points: 0.07 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
USACO US-Open 2008 - Bronze Division
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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 \le R \le 100)~ hàng và ~C~ ~(1 \le C \le 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 nhưng không được đi vào ô có đá hay đi ra khỏi đồng cỏ.

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é)

Input

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

Output

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

Sample Input

5 6
B...*.
..*...
.**.*.
..***.
*..*.C

Sample Output

9

Comments

Please read the guidelines before commenting.



  • 7
    Duy_e   commented on June 10, 2021, 3:03 p.m.

    em nghĩ là nên để thêm là k được đi vào những ô có đá


    • 3
      leduykhongngu   commented on June 10, 2021, 3:05 p.m.

      Mình đã sửa ở đề bài rồi nhé. Cám ơn bạn!


  • 24
    I_love_Hoang_Yen   commented on April 9, 2021, 9:53 p.m.

    Input đảm bảo chỉ có 1 ô B và 1 ô C, và luôn tồn tại đường đi.