BFS08

Submit solution
Points: 10
Time limit: 1.0s
Memory limit: 512M
Problem type

Cho một bảng hình chữ nhật được biểu diễn bằng một ma trận kích thước \(N ×M\), trong đó:

  • Ô có giá trị \(0\) là ô trống, có thể di chuyển qua.

  • Ô có giá trị \(1\) là ô tường, không thể di chuyển qua.

Người chơi bắt đầu tại ô \((x,y)\) và cần di chuyển đến ô \((u,v)\) bằng cách di chuyển theo 4 hướng: trên, dưới, trái, phải.

Yêu cầu: Bạn cần tìm đường đi ngắn nhất ô \((x,y)\) và cần di chuyển đến ô \((u,v)\), nếu có. Nếu không có đường đi, trả về -1.

Input

  • Dòng đầu tiên chứa hai số nguyên \(N , M (1 ≤ N,M ≤ 1000) \)

  • Dòng thứ hai chứa hai số nguyên \(x,y (0≤x<N;0≤y<M).\)

  • Dòng thứ ba chứa hai số nguyên \(u,v (0≤u<N;0≤v<M).\)

  • Tiếp theo là \(N\) dòng, mỗi dòng chứa \(M\) số nguyên 0 hoặc 1, biểu diễn mê cung.

Output

  • Ghi độ dài của đường đi ngắn nhất từ điểm bắt đầu đến điểm kết thúc. Nếu không có đường đi, trả về -1.

Sample Input

5 5
0 0
4 4
0 1 0 0 0
0 1 1 1 0
0 0 0 1 0
1 1 0 0 0
0 0 0 1 0

Sample Output

8

Sample Input

7 7
0 0
6 6
0 0 0 0 0 0 0
1 1 1 1 1 1 0
1 1 1 1 1 1 0
1 1 1 1 1 1 0
1 1 1 1 1 1 0
1 1 1 1 1 1 0
0 0 0 0 0 0 0

Sample Output

7

Comments