Робінзон
Робінзон
Нарешті Робінзон скачав з Інтернету фото свого острова і зможе побудувати хатину на південному узбережжі. Острів Робінзона омивається з усіх боків океаном і має внутрішні водойми. Фото - прямокутна матриця розміром N x M клітин, де 0 – клітина води, 1 – клітина суші. Стара оселя Робінзона знаходиться в клітині з координатами A, B. Допоможіть Робінзону вибрати клітину C, D на південному узбережжі для побудови нової хатини, так, щоб час T руху між хатинами був мінімальний. Якщо таких клітин декілька, достатньо вказати одну з них. Рухається Робінзон по сусідніх клітинах через спільні сторони і витрачає 1 год на клітину суші і 3 год на клітину води (час, затрачений на першу і останню клітини маршруту, теж враховується). Клітина південного узбережжя - остання 1 в кожному стовпчику матриці.
Вхідні дані:
В першому рядку числові значення N, M, A, B - натуральні, не більші 100. В N наступних рядках по M чисел 0 або 1 в кожному.
Вихідні дані:
В першому рядку T– мінімальний час руху між хатинами. У другому координати C, D нової хатини на південному узбережжі.
4 5 1 3 0 1 1 0 0 0 1 0 1 0 1 0 0 0 1 1 1 1 1 1
7 4 2