Nguồn: https://www.hackerrank.com/challenges/castle-on-the-grid/problem

Bạn được cho một lưới gồm \(n \times n\) ô vuông, các dòng và cột được đánh số từ 0 đến \(n - 1\), trên mỗi ô vuông có thể là ô rỗng hoặc chứa chướng ngại vật. Nhiệm vụ của bạn là tìm cách di chuyển từ ô \((sx,sy)\) đến ô \((gx,gy)\) sao cho số lần di chuyển là ít nhất. Biết rằng từ 1 ô \((x,y)\) có thể di chuyển dọc theo hàng hoặc cột cho đến khi gặp chướng ngại vật hoặc đến biên của lưới.

Dữ liệu vào:

+ Dòng đầu tiên ghi số nguyên dương \(n\ (1 \leq n \leq 100)\).

+ \(n\) dòng tiếp theo, mỗi dòng ghi \(n\) ký tự, mỗi ký tự hoặc là dấu ‘.’ hoặc là dấu ‘X’. Trong đó dấu ‘.’ Cho biết ô rỗng, dấu ‘X’ cho biết ô có chướng ngại vật.

+ Dòng cuối cùng ghi lần lượt 4 số nguyên là \(sx,sy,gx,gy\ (0 \leq sx,sy,gx,gy < n)\)

Kết quả: Một số nguyên duy nhất là kết quả bài toán.

Ví dụ:

Grid.inp	Grid.out
3 .X. .X. … 0 0 0 2	3