Robinzon

Robinzon nəhayət İnternetdən öz adasının şəklini yüklədi və cənub sahilində bir daxma tikmək istəyir. Robinzonun adası hər tərəfdən okeanla əhatə olunub və daxili su hövzələri mövcuddur. Şəkil N × M ölçüsündə düzbucaqlı bir matrisdir, burada 0 su hüceyrəsini, 1 isə quru hüceyrəsini təmsil edir. Robinzonun köhnə evi A, B koordinatlarında yerləşir. Robinzona cənub sahilində yeni daxma tikmək üçün C, D hüceyrəsini seçməkdə kömək edin ki, daxmalar arasında hərəkət vaxtı T minimal olsun. Əgər belə hüceyrələr bir neçədirsə, onlardan birini göstərmək kifayətdir. Robinzon qonşu hüceyrələr arasında ortaq tərəflər vasitəsilə hərəkət edir və quru hüceyrəsinə keçmək 1 saat, su hüceyrəsinə keçmək isə 3 saat tələb edir (marşrutun ilk və son hüceyrələrinə sərf olunan vaxt da nəzərə alınır). Cənub sahilinin hüceyrəsi matrisin hər sütunundakı sonuncu 1-dir.

Giriş məlumatları:

Birinci sətirdə N, M, A, B — təbii ədədlər, 100-dən böyük deyil. Növbəti N sətirdə hər birində M ədəd 0 və ya 1.

Çıxış məlumatları:

Birinci sətirdə T — daxmalar arasında hərəkətin minimal vaxtı. İkinci sətirdə cənub sahilindəki yeni daxmanın C, D koordinatları.