Phá tường ít nhất trong mê cung
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho mê cung lưới kích thước $N \times M$ gồm các ký tự . (ô trống) và # (tường).
Bạn xuất phát tại ô $(1, 1)$ và muốn đi đến ô $(N, M)$. Mỗi bước bạn có thể đi sang một trong 4 ô kề cạnh.
Đi vào ô . không mất chi phí, còn đi vào ô # mất chi phí $1$ (phá bức tường tại ô đó).
Hãy tìm tổng chi phí nhỏ nhất để đi từ $(1, 1)$ đến $(N, M)$ (tính cả chi phí tại ô $(1, 1)$ nếu nó là #).
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, M$.
- $N$ dòng tiếp theo, mỗi dòng là một xâu độ dài $M$ gồm
.và#.
Dữ liệu ra
In ra một số nguyên duy nhất là chi phí nhỏ nhất.
Ví dụ
| Input | Output |
|---|---|
| 3 4 .#.. .##. ..#. |
1 |
Giới hạn
$1 \le N, M \le 1000$.
Community Discussion