Kayak

Kış olimpiyatlarındaki kayak parkuru M x N lik (1 <= M,N <= 500) bir arazide belirlenmiştir. Her birim kare 0 .. 1,000,000,000 arasında bir yüksekliğe sahiptir.

Bazı kareler parkur yolu olarak seçilmiştir. Kış olimpiyatı organizatörleri parkur boyunca bir zorluk seviyesi (D) olması konusunda anlaşırlar. Bu şekilde bir ineğin kayarken bir kareden diğerine geçebilmesi için aralarındaki yükseklik D yi aşamayacak şekilde olmaktadır. İnek kayarken sadece güney, kuzey, doğu ve batı yönündeki komşu birim karelere gidebilmektedir.

PROBLEM ADI: ccski

GİRDİ ŞEKLİ:

* Satır 1: M ve N sayıları.

* Satır 2..1+M: Her satır N tane yükseklik içermektedir.

* Satır 2+M..1+2M: Her satır toplam N tane olmak üzere 0 ya da 1 değerlerini içermektedir. Bu değerler parkurda gidilmesi gereken yolları göstermektedir.

ÖRNEK GİRDİ (dosya ccski.in):

3 5

20 21 18 99 5

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

GİRDİ AÇIKLAMASI:

Parkur 3 x 5 lik bir arazide tanımlanmıştır. Sol ve sağ üst, sağ alt gidilmesi gereken yerleri göstermektedir.

ÇIKTI ŞEKLİ:

* Satır 1: Zorluk seviyesi (Gidilmesi gereken tüm yerlere ulaşabilecek şekilde en küçük D).

ÖRNEK ÇIKTI (dosya ccski.out):

21

ÇIKTI AÇIKLAMASI:

Eğer D = 21, 3 yere de birbirinden gidilebilir. Eğer D < 21 ise, sağ üstteki noktaya diğer iki yerden varılamaz.

Çözüm Metni :

Reachable(X) diye bir fonksiyon tanımlayalım ki bu fonksiyon bize tüm gidilmesi gereken yerlere gidilebilecek derecede olan X değerinin doğru olup olmadığını versin. Bu sayede farklı X değerleri kullanıp D değerini bulabiliriz. 0 .. 1000000000 arasında tüm X değerleri yerine ikili arama yapıp D değerini elde edebiliriz.

Dmin=0, Dmax=1000000000

while Dmin < Dmax

    X = (Dmin + Dmax) / 2

    if Reachable(X)

        Dmax = X

    else 

        Dmin = X + 1

D = Dmin

Reachable fonksiyonu üstüne bir de gidilmesi gereken noktalar arasındaki yolları belirlemek için bir algoritmaya ihtiyacımız var. Aradaki yükseklik farklı D olacak şekilde belirlemek için DFS ya da BFS kullanabiliriz. Ancak DFS bazı girdilerde çok uzun dallanmalara sebebiyet vereceği için BFS ile bunu belirlemek daha iyi olacaktır.
Her Reachable fonksiyonu çağrılması O(NM) çözüm karmaşıklığına denk gelir. İkili arama fonksiyonu da O(log R) çözüm karmaşıklığındadır. (R 0..1,000,000,000 arasındadır). Toplam çözüm karmaşıklığı O(MN log R) dir.

Soru Linki : http://usaco.org/index.php?page=viewproblem2&cpid=380
Çözüm Kodu :  http://usaco.org/current/data/sol_ccski.html