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

View as PDF
Submit solution
Points: 0.10 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Author:
bedao
Problem source:
Kỳ thi Học sinh giỏi THPT TPHCM 2021
Problem types
Allowed languages
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

Comments

Please read the guidelines before commenting.


  • 0
    duonggsimp  commented on July 26, 2024, 2:59 a.m. ← edit 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


  • -4
    khanhlani  commented on July 25, 2024, 12:22 p.m.

    Hà Ly cute vãi


  • 0
    chi_nhan  commented on March 4, 2024, 4:43 p.m. ← edit 4

    Bài này hay (ko spam)


    • 0
      thanhsda  commented on April 20, 2024, 10:14 a.m.

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


      • 3
        RussVN123  commented on May 4, 2024, 2:23 p.m. ← edit 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.


        • 0
          messizutaki  commented on Dec. 1, 2024, 9:56 a.m.

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


        • 4
          dxz  commented on July 8, 2024, 1:42 p.m.

          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 ạ


          • 0
            RussVN123  commented on July 9, 2024, 11:19 a.m.

            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.


  • -29
    chithien19112008  commented on Feb. 20, 2024, 12:05 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.