MÊ CUNG – TỐI THIỂU SỐ LẦN ĐỔI HƯỚNG

Mã bài: DOIHUONG
Nguồn: AtCoder Typical 90 – Bài 043, Maze Challenge with Lack of Sleep (★4)
Đề gốc: https://atcoder.jp/contests/typical90/tasks/typical90_aq
Thời gian: 2 giây (theo AtCoder)
Bộ nhớ: 1024 MiB (theo AtCoder)
Đọc/ghi: standard input (stdin) / standard output (stdout)

Đề bài

Cho một mê cung hình chữ nhật gồm H hàng và W cột. Các hàng được đánh số từ 1 đến H theo chiều từ trên xuống; các cột được đánh số từ 1 đến W theo chiều từ trái sang phải.

Mê cung được biểu diễn bằng H xâu ký tự, mỗi xâu có đúng W ký tự:

• Dấu . biểu thị ô trống, có thể đi qua.
• Dấu # biểu thị ô tường, không thể đi qua.

Bạn xuất phát tại ô (r_s, c_s) và cần đến ô (r_t, c_t). Mỗi lần di chuyển, bạn chỉ được chuyển sang một ô trống kề cạnh theo một trong bốn hướng: lên, xuống, trái hoặc phải. Không được đi ra ngoài mê cung.

Điều làm bạn mệt mỏi không phải số bước đi, mà là số lần thay đổi hướng di chuyển. Một lần đổi hướng được tính khi hướng đi ở bước hiện tại khác với hướng đi ở bước liền trước. Bước đi đầu tiên không tính là đổi hướng.

Yêu cầu: Tìm số lần đổi hướng nhỏ nhất để đi từ ô xuất phát đến ô đích. Đường đi tối ưu theo số lần đổi hướng có thể không phải là đường đi ít bước nhất.

Đề bảo đảm luôn tồn tại ít nhất một đường đi hợp lệ từ ô xuất phát đến ô đích.

Dữ liệu vào

Dữ liệu được nhập theo định dạng:

H W
r_s c_s
r_t c_t
S_1
S_2
...
S_H

Trong đó:

• H, W lần lượt là số hàng và số cột.
• (r_s, c_s) là vị trí xuất phát, tính từ 1.
• (r_t, c_t) là vị trí đích, tính từ 1.
• S_i là xâu có độ dài W, mô tả hàng thứ i của mê cung (với i từ 1 đến H).

Kết quả

In ra một số nguyên duy nhất: số lần đổi hướng ít nhất cần thực hiện.

Ràng buộc

• 2 ≤ H ≤ 1000 và 2 ≤ W ≤ 1000.
• 1 ≤ r_s ≤ H và 1 ≤ r_t ≤ H.
• 1 ≤ c_s ≤ W và 1 ≤ c_t ≤ W.
• (r_s, c_s) ≠ (r_t, c_t).
• Các chỉ số và kích thước đều là số nguyên.
• Mỗi ký tự trong mê cung chỉ có thể là . hoặc #.
• Hai ô xuất phát và đích đều là ô trống.
• Luôn có đường đi từ ô xuất phát đến ô đích.

Ví dụ 1

Input

3 3
1 1
3 3
..#
#.#
#..

Output

2

Giải thích: Có thể đi theo các ô (1,1) → (1,2) → (2,2) → (3,2) → (3,3). Hướng di chuyển thay đổi hai lần: phải → xuống và xuống → phải.

Ví dụ 2

Input

3 3
2 1
2 3
#.#
...
#.#

Output

0

Giải thích: Chỉ cần đi sang phải hai bước, không phải đổi hướng.

Ví dụ 3

Input

4 6
2 1
1 5
...#..
.#.##.
.#....
...##.

Output

5

Lưu ý

• Mục tiêu là tối thiểu số lần đổi hướng, không phải số ô đã đi qua.
• Chỉ cần xuất đáp án, không cần in ra đường đi.
• Bài dùng chương trình C++17 độc lập, nhập từ stdin và xuất ra stdout (không yêu cầu dạng hàm class Solution).

Bản trình bày dùng để luyện tập, dựa trên đề AtCoder Typical 90 số 043. Các bộ test bổ sung trong gói CLAOJ do người biên soạn tự tạo, không phải test chính thức của AtCoder.