Phá tường ít nhất trong mê cung

Buổi 41 — SPFA & Bellman-Ford Buổi 69-70 — Mock Tổng hợp Graphs
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$.

Draft saved