Khám phá hang động
Cường đang thám hiểm một hang động. Bản đồ hang động này có dạng một bảng chữ nhật có $M$ hàng, $N$ cột. Cường hiện tại đang ở ô $(1,1)$, cậu muốn tìm đường đi đến ô $(M,N)$. Cường có thể di chuyển tới ô $(i,j+1)$ hoặc ô $(i+1,j)$ nếu cậu đang đứng tại ô $(i,j)$ và cậu sẽ không được di chuyển ra khỏi bảng.
Mỗi ô trong hang có thể là tường đá. Ô ở hàng thứ $i$ và cột thứ $j$ là ô $(i,j)$. Ô $(i,j)$ là tường đá khi $c_{i,j}=x$, nếu không $c_{i,j}=o$.
Cường có thể di chuyển qua lại giữa các ô không phải tường đá. Tuy nhiên, cậu cũng có thể phá các bức tường đá này. Mỗi lần như vậy, cậu đều tốn năng lượng. Và sau khi tường đá bị phá, cậu có thể đi vào ô đó được.
Hãy giúp Cường tìm đường đi ra khỏi hang động sao cho tổng số tường đá cậu phá là nhỏ nhất.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên $M,N \ (1\le M,N \le 500)$;
- $M$ dòng tiếp theo, mỗi dòng chứa $N$ kí tự $c_{i,j} \ (c_{i,j} \in {
x , o} )$.
Dữ liệu đảm bảo ô xuất phát và ô kết thúc không có tường đá.
Kết quả
- Kết quả bài toán.
Ví dụ
Ví dụ 1
input
5 5
ooxxo
xxoxx
ooooo
xxxxx
ooxoo
output
2
Comments