Link Sub: http://vn.spoj.com/problems/VMUNCH/
Người Gửi: Dương Lee
- Problem:
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
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.
Example:
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.
Input
5 6
B...*.
..*...
.**.*.
..***.
*..*.C
Output:
9
- Solution:
- Các bước làm: + Đọc dữ liệu (+ Tìm luôn vị trí của 'B' và 'C').
+ Khởi tạo liên kết: Với mỗi ô của bãi cỏ thì xét các ô kề cạnh xung quanh nó xem ô nào đi được thì tạo liên kết (v[][][]).
+ Duyệt BFS (Áp dụng theo quy tắc thông thường của duyệt BFS) + mảng dấu vết (mark[con][con] = mark[cha][cha]+1).
-> in ra mark [C][C];