Sân Golf (OLP 10 - 2018) - LQDOJ: Le Quy Don Online Judge

Sân Golf (OLP 10 - 2018)

Tác giả:

Dạng bài

Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Sân golf được biểu diễn bởi một lưới kích thước \(M \times N (1≤M, N≤500)\). Mỗi ô của
lưới có độ cao trong khoảng 0 đến 109 so với mực nước biển.

Tại một vài ô trong lưới này là các vị trí có đặt lỗ, tức là nơi vận động viên sẽ đánh
bóng rơi vào đó và bắt buộc sẽ đi đến đó để nhặt bóng.

Ban tổ chức của Olympics muốn đánh giá độ chênh lệch độ cao \(D\) của sân golf bằng
cách làm như sau:

Cho một nhân viên bắt đầu di chuyển từ một vị trí đặt lỗ bất kỳ đến một trong bốn ô
kề cạnh với ô đang đứng, có trị tuyệt đối chênh lệch độ cao không quá \(D\). Tại ô mới
này, anh ta lại di chuyển tiếp sang một trong bốn ô kề cạnh có trị tuyệt đối chênh lệch
độ cao không quá \(D\). Cứ thế tiếp tục cho đến khi có thể đến được tất cả các lỗ.

Yêu cầu:

Hãy xác định độ chênh lệch độ cao \(D\) nhỏ nhất mà từ một lỗ bất kỳ có thể
đến được tất cả các lỗ còn lại.

Input

Dòng 1: chứa 2 số nguyên \(M, N\).
\(M\) dòng tiếp theo: mỗi dòng chứa \(N\) số nguyên là độ cao của ô.
\(M\) dòng tiếp theo: mỗi dòng chứa \(N\) giá trị là 0 hoặc 1, trong đó ô có giá trị 1
cho biết tại vị trí đó có lỗ, ngược lại thì tại đó không có lỗ.

Các số ghi trên cùng một dòng cách nhau bởi ít nhất một kí tự trắng.

Kết quả

Một dòng duy nhất ghi số nguyên dương \(D\) cần tìm.

Example

Test 1

Input

3 5
25 21 18 76 15
19 22 20 16 26
18 17 40 60 80
1 0 0 0 1
0 0 0 0 0
0 0 0 0 1

Output

Note

Với \(D = 20\): từ lỗ (1,1)
ta đến được các lỗ (1,5),
(3,5) hoặc theo hướng
ngược lại.
Với \(D = 19\), từ lỗ (1,1)
hoặc lỗ (1,5) ta không thể
đi đến được lỗ (3,5).

Nguồn: Olympic 30/4 năm 2018.

Bình luận

Ta chỉ quan tâm các ô mang giá trị 1
Duyệt qua các ô để tìm tọa độ của chúng rồi đưa vào 1 vector
Nhận xét : Nếu H là độ cao được chọn thì từ 1 tọa độ mang giá trị 1 bất kì ta đều có thể đến được các ô mang giá trị 1 khác
Do đó sử dụng thuật toán chặt nhị phân để tìm độ cao . Giả sử độ cao là H thì tại 1 ô mang giá trị 1 bất kì ta sẽ dụng thuật toán loang để tìm những ô có thể đến nếu chỉ dùng độ cao tối đa là H.
Sau khi loang ta chỉ cần kiểm tra các ô mang giá trị 1 ta đã lưu trong vector có được loang tới hay không ?
Nếu được ta thử độ cao thấp hơn . Ngược lại ta thử độ cao cao hơn

Độ phức tạp thuật toán : O(nmlog(1e9))

C++

void loang ( int l, int r, int value )
{
    ktra[l][r] = true ;
    if (r < m)
        if (abs(a[l][r] - a[l][r+1]) <= value)
            if (ktra[l][r+1] == false)
                loang(l,r+1,value);
    if (r > 1)
        if (abs(a[l][r] - a[l][r-1]) <= value)
            if (ktra[l][r-1] == false)
                loang(l,r-1,value);
    if (l < n)
        if (abs(a[l][r] - a[l+1][r]) <= value)
            if (ktra[l+1][r] == false)
                loang(l+1,r,value);
    if (l > 1)
        if (abs(a[l][r] - a[l-1][r]) <= value)
            if (ktra[l-1][r] == false)
                loang(l-1,r,value);
}
bool check( int k, int l, int r)
{
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
            ktra[i][j] = false;
    loang ( l, r, k); /// l , r là tọa độ 1 ô bất kì mang giá trị 1.
    for(auto x : address) /// mảng address lưu các tọa độ các ô mang giá trị là 1
        if (ktra[x.fi][x.se] == false) return false;
    return true;
}