Mountain Walking

Xem dạng PDF
Gửi bài giải
Điểm: 0,16 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Nguồn bài:
USACO 2003 US Open
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một bản đồ kích thước ~N \times N~ ~(2 \le N \le 100)~, mỗi ô mang giá trị là độ cao của ô đó ~(0 \le~ độ cao ~\le 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.

Input

  • 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 ô.

Output

Một số nguyên là chênh lệch cao độ nhỏ nhất.

Sample Input

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

Sample Output

2

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    lamdt  đã bình luận lúc 18, Tháng 8, 2025, 11:46

    Bài này dùng dijkstra cũng ổn mà đúng không ?


  • 8
    pppssslc  đã bình luận lúc 16, Tháng 7, 2025, 9:08

    My solve:

    CNP + DFS/BFS:

    • Chặt nhị phân giá trị ~x~ là hiệu giữa số lớn nhất và nhỏ nhất trên đường đi từ ~(1, 1)~ tới ~(n, n)~.
    • Giá trị ~x~ càng lớn thì càng dễ thỏa mãn.
    • Kiểm tra giá trị ~x~:
    • Ta BFS/DFS từ ~(1, 1)~ với điều kiện các ô đều nằm trong khoảng ~[0, x]~, ~[1, x + 1]~, ... hoặc ~[110 - x, 110]~.
    • Nếu ta có thể BFS/DFS tới ~(n, n)~ thì ~x~ thỏa mãn.

  • -80
    letanthucbao  đã bình luận lúc 4, Tháng 8, 2023, 9:58

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.