HSG THPT TPHCM 2021 - Tìm đường

Xem dạng PDF
Gửi bài giải
Điểm: 0,10 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Tác giả:
bedao
Nguồn bài:
Kỳ thi Học sinh giỏi THPT TPHCM 2021
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Bạn An đang đứng ở vị trí có tọa độ ~(1,1)~ trên bản đồ và muốn đi đến thành phố ByteCity ở tọa độ ~(N,N)~.

Đây là bản đồ hình vuông, bản đồ có chứa các độ cao ~A[i][j]~ tại mỗi tọa độ ~(i,j)~. Bạn An chỉ đi được từ một ô sang các ô kề cạnh.

Yêu cầu: Bạn An không giỏi leo lên (hoặc xuống) đồi nên muốn nhờ bạn lập trình tìm con đường sao cho độ lệch lớn nhất của độ cao hai ô kề cạnh là nhỏ nhất có thể được. Độ lệch của độ cao hai ô được hiểu là trị tuyệt đối của hiệu độ cao của hai ô này.

Input

Dòng đầu tiên ghi hai số nguyên dương ~N~ ~(1 < N \le 500)~

~N~ dòng tiếp theo, mỗi dòng ghi ~N~ số nguyên dương ~A[i][j]~ cho biết độ cao của các vị trí tương ứng tại dòng i và cột j trên bản đồ ~(0 \le A[i][j] \le 10^6)~

Output

Một số nguyên dương duy nhất cho biết độ lệch lớn nhất của độ cao hai ô kề cạnh trên con đường tìm được.

Sample Input 1

4
3 5 7 7
2 4 4 7
3 3 5 4
9 5 8 5

Sample Output 1

1

Bình luận

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


  • 0
    duonggsimp  đã bình luận lúc 26, Tháng 7, 2024, 2:59 ← sửa 2

    bài này chặt nhị chặt phân kq tìm khoảng cách r dfs hay bfs xem thử khoảng cách có phù hợp k xong lưu biến res


  • -6
    khanhlani  đã bình luận lúc 25, Tháng 7, 2024, 12:22

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


  • 1
    chi_nhan  đã bình luận lúc 4, Tháng 3, 2024, 16:43 ← sửa 4

    Bài này hay (ko spam)


    • -1
      thanhsda  đã bình luận lúc 20, Tháng 4, 2024, 10:14

      mà khó quá. anh chi em ý tưởng cái đi


      • 3
        RussVN123  đã bình luận lúc 4, Tháng 5, 2024, 14:23 ← sửa 8

        Spoiler

        Để ý thấy N khá nhỏ nên có thể BFS nhiều lần. Để tìm được độ lệch lớn nhất đường đi mà nhỏ nhất thì giống như loang vậy , nếu loang ra mà loang đến được (N,N) chỉ với độ lệch lớn nhất là X thì thỏa mãn. Mà X càng lớn thì càng dễ tìm được đường nên từ đó ta có thể chặt nhị phân kết hợp BFS.


        • -2
          messizutaki  đã bình luận lúc 1, Tháng 12, 2024, 9:56

          tìm kiếm nhị phân ra X bằng cách nào v ạ


        • 4
          dxz  đã bình luận lúc 8, Tháng 7, 2024, 13:42

          Cho mình hỏi, mình bfs như thế nào để tìm ra các đường đi từ (1;1) đến (n;n) với ạ


          • 2
            RussVN123  đã bình luận lúc 9, Tháng 7, 2024, 11:19

            giả sử bạn ở vị trí i,j thì có nghĩa tồn tại đường đi từ 1,1 đến vị trí i,j có độ lệch lớn nhất đường <=X nên ta cần bfs từ đỉnh i,j đến các đỉnh kề nó chưa thăm và thỏa mãn độ lệch <=X. Nếu sau khi bfs mà ô n,n được thăm thì có nghĩa là tồn tại đường đi từ 1,1, đến n,n thỏa mãn độ lệch lớn nhất đường <=X và nếu thế ta sẽ giảm X xuống để tìm X cực tiểu. Ngược lại tăng X lên để tìm X.


  • -33
    chithien19112008  đã bình luận lúc 20, Tháng 2, 2024, 0:05

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