MTWALK spoj – Mountain Walking

Nguồn đề bài http://vn.spoj.com/problems/MTWALK/

1. Đề bài MTWALK spoj

Cho một bản đồ kích thước NxN (2 <= N <= 100), mỗi ô mang giá trị là độ cao của ô đó (0 <= độ cao <= 110). Bác John và bò Bessie đang ở ô trên trái (dòng 1, cột 1) và muốn đi đến cabin (dòng N, cột N). Họ có thể đi sang phải, trái, lên trên và xuống dưới nhưng không thể đi theo đường chéo. Hãy giúp bác John và bò Bessie tìm đường đi sao cho chênh lệch giữa điểm cao nhất và thấp nhất trên đường đi là nhỏ nhất.
Dữ liệu
Dòng 1: N
Dòng 2..N+1: Mỗi dòng chứa N số nguyên, mỗi số cho biết cao độ của một ô.
Kết quả
Một số nguyên là chênh lệch cao độ nhỏ nhất.

Ví dụ
Dữ liệu
5
1 1 3 6 8
1 2 2 5 5
4 4 0 3 3
8 0 2 3 4
4 3 0 2 1
Kết quả
2

2. Hướng dẫn MTWALK spoj

Dùng chặt nhị phân.

Hàm kiểm tra ta dùng BFS. Bài toán đưa về bài toán con: với độ chênh lệch nhỏ nhất là k, ta có đường đi từ ô (1,1) tới ô (n,n) hay không.

Ôi khó nói thuật cụ thể quá! Nếu các bạn không hiểu thì có thể cmt để bình luận thêm. Mình sẽ giải đáp. Cảm ơn!