Gặm cỏ

Xem dạng PDF

Gửi bài giải


Điểm: 0,07 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
USACO US-Open 2008 - Bronze Division
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • -1
    hozybowl  đã bình luận lúc 12, Tháng 9, 2024, 10:34

    bài này dùng bfs đc thôi ạ tại dfs chạy không nổi


  • 3
    MalazeKL  đã bình luận lúc 15, Tháng 8, 2024, 12:37

    bài này là bài toán tìm đường đi ngắn nhất trong trường hợp có vật cản không đi qua được, sử dụng BFS nha ae bài này là ví dụ đầu tiên của phần "Ứng dụng BFS để tìm đường đi ngắn nhất trong đồ thị không trọng số" của Vnoi Wiki https://wiki.vnoi.info/algo/graph-theory/breadth-first-search.md


  • -4
    nhan0123456  đã bình luận lúc 7, Tháng 8, 2024, 12:23

    bài này dùng quy hoạch động được không?


    • -4
      MalazeKL  đã bình luận lúc 15, Tháng 8, 2024, 16:53

      mình nghĩ là ko :v


  • -11
    nhan19042007  đã bình luận lúc 12, Tháng 10, 2023, 6:22 chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • 0
      trtduong301  đã bình luận lúc 20, Tháng 12, 2023, 18:19

      ok a


  • 11
    Duy_e  đã bình luận lúc 10, Tháng 6, 2021, 8:03

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


    • 7
      leduykhongngu  đã bình luận lúc 10, Tháng 6, 2021, 8:05

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


  • 48
    I_love_Hoang_Yen  đã bình luận lúc 9, Tháng 4, 2021, 14:53

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